658.Find K Closest Elements

Tags: Medium Binary Search

Links: https://leetcode.com/problems/find-k-closest-elements/

---

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Example 2:

Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]

Note:

1. The value k is positive and will always be smaller than the length of the sorted array.
2. Length of the given array is positive and will not exceed 10^4
3. Absolute value of elements in the array and x will not exceed 10^4

---

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        vector<int> res;
        int pos = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
        int cnt = 0, n = arr.size();

        if (pos == 0) {
            for (int i = 0; i < k; ++i){
                res.push_back(arr[i]);
            }
            return res;
        }
        else if (pos == n) {
            for (int i = n - k; i < n; ++i) {
                res.push_back(arr[i]);
            }
            return res;
        }

        int left = pos - 1, right = pos;
        while (cnt != k) {
            if (left < 0) {
                res.push_back(arr[right]);
                ++right;
                ++cnt;
                continue;
            }
            if (right >= n) {
                res.push_back(arr[left]);
                --left;
                ++cnt;
                continue;
            }
            if (x - arr[left] <= arr[right] - x) {
                res.push_back(arr[left]);
                --left;
                ++cnt;
            }
            else{
                res.push_back(arr[right]);
                ++right;
                ++cnt;
            }
        }
        sort(res.begin(), res.end());
        return res;   
    }
};

Runtime: 112 ms, faster than 29.91% of C++ online submissions for Find K Closest Elements.
Memory Usage: 13.6 MB, less than 16.67% of C++ online submissions for Find K Closest Elements.

这种方法显然是最朴素的方法，先找到第一个不小于x的数，往左右两边探索，注意不要超过边界即可,时间复杂度$O(logn + k)$。

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int left = 0, right = arr.size() - k;

        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (x - arr[mid] > arr[mid + k] - x) left = mid + 1;
            else right = mid;
        }

        return vector<int>(arr.begin() + left, arr.begin() + left + k);
    }
};

Runtime: 100 ms, faster than 77.70% of C++ online submissions for Find K Closest Elements.
Memory Usage: 12.9 MB, less than 83.33% of C++ online submissions for Find K Closest Elements.

这种方法是搜索子数组的起始位置！