Find K Closest Elements

• Lintcode : 460 / Leetcode : 658
• Level : Medium

Problem

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^410
​4
​​ 
Absolute value of elements in the array will not exceed 10^410
​4
​​

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(logn + k)
space: O(k)

Answer

class Solution {
public:
    vector<int> kClosestNumbers(vector<int> &A, int target, int k) {
        // corner case
        if (A.size() < k) return A;

        int index = findLastLessAndEqual(A, target);
        vector<int> ans;
        countK(A, target, k, ans, index);
        return ans;
    }
    int findLastLessAndEqual (vector<int> &A, int target) {
        int l = 0, r = A.size() - 1;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (A[mid] <= target) {
                l = mid;
            }else {
                r = mid;
            }
        }
        if (A[r] <= target) return r;
        if (A[l] <= target) return l;
        return -1;
    }
    void countK(vector<int> &A, int target, int k, vector<int> &ans, int index) {
        int left = index, right = index + 1;
        while (k && left >= 0 && right < A.size()) {
            while (k && left >= 0 && right < A.size() && abs(A[left] - target) <= abs(A[right] - target)) {
                ans.push_back(A[left--]);
                k--;
            }
            while (k && left >= 0 && right < A.size() && abs(A[left] - target) > abs(A[right] - target)) {
                ans.push_back(A[right++]);
                k--;
            }
        }
        while (k && left >= 0) {
            ans.push_back(A[left--]);
            k--;
        }
        while (k && right < A.size()) {
            ans.push_back(A[right++]);
            k--;
        }
    }
};

tags: Binary Search

​