leetcode 658. 找到 K 个最接近的元素

658. 找到 K 个最接近的元素

法一：

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        vector<pair<int,int>> dist;
        vector<int> res;
        int size = arr.size();
        for(int i = 0;i < size;++i){
            dist.emplace_back(abs(arr[i]-x),i);
        }
        sort(dist.begin(),dist.end());
        for(int i = 0;i < k;++i)  res.emplace_back(arr[dist[i].second]);
        sort(res.begin(),res.end());
        return res;
    }
};

法二：二分查找 + 双指针；不需考虑各种奇怪的边界条件，双指针会帮你判断

class Solution {
public:
//可以将数组 arr 分成两部分，前一部分所有元素 [0,left] 都小于 x，后一部分所有元素 [right,n−1] 都大于等于 x
//left 与 right 都可以通过二分查找获得。left 和 right 指向的元素都是各自部分最接近 x 的元素
//因此我们可以通过比较 left 和 right 指向的元素获取整体最接近 x 的元素
//如果 x−arr[left]≤arr[right]−x，那么将 left 减一，否则将 right 加一
//相应地，如果 left 或 right 已经越界，那么不考虑对应部分的元素。
//最后，区间 [left+1,right−1] 的元素就是我们所要获得的结果，返回答案既可。

    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        //lower_bound用于在有序区间中查找第一个大于或等于给定值的元素的位置，基于二分查找实现
        int right = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
        int left = right - 1,size = arr.size();
        while(k--){
            if(left < 0)  ++right;
            else if(right >= size)  --left;
            else if(x - arr[left] <= arr[right] - x)  --left;
            else  ++right;
        }
        return vector<int>(arr.begin() + left + 1,arr.begin() + right);//表示返回[left+1,right−1]的元素
    }
};