给一个目标数 target, 一个非负整数 k, 一个按照升序排列的数组 A。在A中找与target最接近的k个整数。返回这k个数并按照与target的接近程度从小到大排序，如果接近程度相当，那么小的数排在前面。
k是一个非负整数，并且总是小于已排序数组的长度。
给定数组的长度是正整数, 不会超过 10^4
数组中元素的绝对值不会超过 10^4
在线评测地址：LintCode 领扣
样例 1:
输入: A = [1, 2, 3], target = 2, k = 3
输出: [2, 1, 3]
样例 2:
输入: A = [1, 4, 6, 8], target = 3, k = 3
输出: [4, 1, 6]
【题解】
直接在数组中二分查找 target, 如果不存在则返回大于 target 的最小的或者小于 target 的最大的元素均可.
然后使用两根指针从该位置开始向两端遍历, 每次把差值比较小的元素放入答案中然后将该指针向边界方向移动一下即可.
public class Solution {
/**
* @param A an integer array
* @param target an integer
* @param k a non-negative integer
* @return an integer array
*/
public int[] kClosestNumbers(int[] A, int target, int k) {
int[] result = new int[k];
if (A == null || A.length == 0) {
return A;
}
if (k > A.length) {
return A;
}
int index = firstIndex(A, target);
int start = index - 1;
int end = index;
for (int i = 0; i < k; i++) {
if (start < 0) {
result[i] = A[end++];
} else if (end >= A.length) {
result[i] = A[start--];
} else {
if (target - A[start] <= A[end] - target) {
result[i] = A[start--];
} else {
result[i] = A[end++];
}
}
}
return result;
}
private int firstIndex(int[] A, int target) {
int start = 0, end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] < target) {
start = mid;
} else if (A[mid] > target) {
end = mid;
} else {
end = mid;
}
}
if (A[start] >= target) {
return start;
}
if (A[end] >= target) {
return end;
}
return A.length;
}