Given a target number, a non-negative integerkand 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.

Have you met this question in a real interview?

Yes

Example

Given A =[1, 2, 3], target =2and k =3, return[2, 1, 3].

Given A =[1, 4, 6, 8], target =3and k =3, return[4, 1, 6].

Challenge

O(logn + k) time complexity.

class Solution {
public:
    /**
     * @param A an integer array
     * @param target an integer
     * @param k a non-negative integer
     * @return an integer array
     */
    vector<int> kClosestNumbers(vector<int>& A, int target, int k) {
        // Write your code here
        vector<int> res;
        if (A.size() < k)
            return res;
        int index = findIndex(A, target);

        int left = index - 1, right = index;

        for (int i = 0; i < k; ++i) {
            if (left < 0) {
                res.push_back(A[right++]);
            } else if (right >= A.size()) {
                res.push_back(A[left--]);
            } else {
                if (target - A[left] <= A[right] - target)
                    res.push_back(A[left--]);
                else
                    res.push_back(A[right++]);
            }
        }


        return res;
    }

    int findIndex(vector<int>& A, int target) {
        int start = 0, end = A.size() - 1;
        while (start + 1 < end) {
            int mid = start + (end - start >> 1);
            if (A[mid] < target)
                start = mid;
            else
                end = mid;
        }
        if (A[start] >= target)
            return start;
        if (A[end] >= target)
            return end;
        return A.size();
    }
};