K Closest Numbers In Sorted Array Show result

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

http://www.lintcode.com/en/problem/k-closest-numbers-in-sorted-array/# ladder only

Discussion

找到第一个大于等于target的地方，用两个指针从这个位置开始左右移动，具体移动哪个取决于difference。

Solution

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) {
        vector<int> result;
        if(A.empty() || k > A.size()) return result;
        //1. find the first position whcih >= target;
        int right = FindFirstLarger(A, target);
        int left = right - 1;
        //2. set up two pointers, move them based on difference
        for(int i=0; i<k; i++) {
            if(left < 0) {
                result.emplace_back(A[right++]);
            } else if(right >= A.size()) {
                result.emplace_back(A[left--]);
            } else {
                if(A[right]-target < target - A[left]) {
                    result.emplace_back(A[right++]);
                } else {//ascending order by number if the difference is same.
                    result.emplace_back(A[left--]);
                }
            }
        }
        return result;
    }
    int FindFirstLarger(vector<int> &A, int target) {
        //using binary search find first number >= target
        int start = 0;
        int end = A.size() -1;
        while(start + 1 < end) {
            int mid = start + (end-start) / 2;
            if(A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if(A[start] >= target) return start;
        return end;
    }
};