题目链接:https://leetcode.cn/problems/find-k-closest-elements/

题目难度:中等

题意

给定一个 排序好 的数组 arr ,两个整数 k 和 x ,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足:

  • |a - x| < |b - x| 或者
  • |a - x| == |b - x| 且 a < b

示例1:

输入:arr = [1,2,3,4,5], k = 4, x = 3
输出:[1,2,3,4]

示例2:

输入:arr = [1,2,3,4,5], k = 4, x = -1
输出:[1,2,3,4]

提示:

  • $1 <= k <= arr.length$
  • $1 <= arr.length <= 10^4$
  • arr 按 升序 排列
  • $-10^4 <= arr[i], x <= 10^4$

题解一:双指针

首先遍历数组找到最接近x的元素位置pos,然后以pos向左右两边遍历,找到符合条件的k的元素,最后返回这k个元素的子数组即可。

时间复杂度:$O(n+k)$

其实还可以优化,无需找到pos,直接定义左指针从0开始,右指针从数组末尾开始,相向寻找,知道左右指针所包含的子数组长度为k即可。

C++代码

class Solution {
public:
    bool check(int a,int b,int x){
        if(abs(a-x)<abs(b-x)) return true;
        else if(abs(a-x)==abs(b-x)&&a<b) return true;
        else return false;
    }
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int n=arr.size();
        //找到和x最接近的数
        int pos=0;
        for(int i=1;i<n;i++){
            if(check(arr[i],arr[pos],x)) pos=i;
        }
      
        vector<int> ans;ans.push_back(arr[pos]);
        int i=pos-1,j=pos+1,cnt=1;
        // cout<<pos<<endl;
        while(i>=0 && j<n && cnt<k){
            if(check(arr[i],arr[j],x)){
                --i;++cnt;
            }else{
                ++j;++cnt;
            }
        }
        while(i>=0 && cnt<k){
            --i;++cnt;
        }
        while(j<n && cnt<k){
            ++j;++cnt;
        }
        return vector<int>(arr.begin()+i+1,arr.begin()+j);
    }
};

题解二:二分查找

由于最后的结果是连续的区间(即子数组),于是转化为求符合条件的最优区间,进而可以转换为最优区间的左边界即可(因为k确定,即长度确定)

左边界最小取值为:0,最大取值为:arr.size()-k。

然后二分查找其最优结果即可。

具体二分思考参考下面链接:https://leetcode.cn/problems/find-k-closest-elements/solution/pai-chu-fa-shuang-zhi-zhen-er-fen-fa-python-dai-ma/

时间复杂度:$O(logn)$

C++代码

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int n=arr.size();
        int l=0,r=n-k;
        while(l<r){
            int mid=(l+r)>>1;
            //尝试从k+1的区间中删除一个元素
            //从而定位最终区间的左边界值
            if(x-arr[mid] > arr[mid+k]-x){
                l=mid+1;
            }else{
                r=mid;
            }
        }
        return vector<int>(arr.begin()+l,arr.begin()+l+k);
    }
};