K Closest Numbers In Sorted Array.png
===================== 解題思路 =====================
二分法先找到最接近的點做為起點（或是跟 target 相同點) 然後以此點的左右鄰點開始比較跟起點的距離 比較小的就存入 然後移動鄰點往兩邊擴散繼續做下一輪的比較
===================== C++ code ====================
<pre><code>
class Solution {
public:
/**
* @param A an integer array
* @param target an integer
* @param k a non-negative integer
* @return an integer array
*/
int findMin(vector<int> &A, int &left, int &right, int target)
{
if(left < 0) return right;
if(right >= A.size()) return left;
return abs(A[left] - target) <= abs(A[right] - target)? left : right;
}
vector<int> kClosestNumbers(vector<int>& A, int target, int k) {
// Write your code here
int left = 0, start = -1, right = A.size() -1;
while(left + 1 < right)
{
int mid = (left + right) / 2;
if(A[mid] == target){
start = mid;
break;
}
if(A[mid] > target) right = mid;
else left = mid;
}
if(start == -1)
{
start = findMin(A, left, right, target);
}
vector<int> res;
left = start -1;
right = start;
for(int i = 0; i < k; i++)
{
int tmp = findMin(A, left, right, target);
if(tmp == left) left--;
else right++;
res.emplace_back(A[tmp]);
}
return res;
}
};
<code><pre>
