Given target, a non-negative integer k and an integer array A sorted in ascending order, find the k closest numbers to target in A, sorted in ascending order by the difference between the number and target. Otherwise, sorted in ascending order by number if the difference is same.

Example
Example 1:
Input: A = [1, 2, 3], target = 2, k = 3
Output: [2, 1, 3]
Example 2:
Input: A = [1, 4, 6, 8], target = 3, k = 3
Output: [4, 1, 6]
Challenge
O(logn + k) time

Notice The value k is a non-negative integer and will always be smaller than the length of the sorted array. Length of the given array is positive and will not exceed 10^4 Absolute value of elements in the array will not exceed 10^4

先找到最近的那个，然后两个指针left和right分别往两边走找到k-1个更近的
public class Solution {
    /**
     * @param A: an integer array
     * @param target: An integer
     * @param k: An integer
     * @return: an integer array
     */
    public int[] kClosestNumbers(int[] A, int target, int k) {

        int[] res = new int[k];
        if(k == 0) return res;
        int start = 0;
        int end = A.length - 1;
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if(A[mid] >= target) end = mid;
            else start = mid;
        }

        int d1 = Math.abs(A[start] - target);
        int d2 = Math.abs(A[end] - target);
        int closest = d1 > d2? end : start;

        int left = closest - 1;
        int right = closest + 1;

        res[0] = A[closest];
        for(int i = 1; i < k; i++) {
            if(right < A.length && (left == -1 || left >= 0 && Math.abs(A[left]-target) > Math.abs(A[right] - target))) {
                res[i] = A[right];
                right++;
            } else if(left >= 0 && (right == A.length || right < A.length && Math.abs(A[left]-target) <= Math.abs(A[right] - target))) {
                res[i] = A[left];
                left--;
            }
        }
        return res;
    }
}

​​