【LeetCode】658.找到K个最接近的数

题目

给定一个 排序好 的数组 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 <= 104
arr 按 升序 排列
-104 <= arr[i], x <= 104

题解

对序列进行: 减x的绝对值的排序
然后取前k个

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        if(arr.size() == k)
            return arr;
        sort(arr.begin(),arr.end(),[=](int &a,int &b){return abs(a-x)==abs(b-x)?a<b:abs(a-x)<abs(b-x);});
        vector<int> res(arr.begin(), arr.begin() + k);
        sort(res.begin(),res.end());
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11

双指针
从两端向中间缩小

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int len = arr.size();
        int left = 0;
        int right = len-1;
        while(right-left >= k)
        {
            int mid = left + (right-left)>1;
            //cout<
            if( abs(arr[left]-x) > abs(arr[right]-x) )
                left+=1;
            else
                right-=1;
        }
        //cout<
        return vector(arr.begin()+left,arr.begin()+right+1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二分查找+双指针
先找到等于x或者偏左的下标
然后左边扩散k位, 右边扩散k位
然后进行压缩,压缩到k个

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int len = arr.size();
        int left = 0;
        int right = len-1;
        while(left<right)
        {
            int mid = ((right-left+1) >> 1) + left;
            cout<<left<<"=="<<mid<<"=="<<right<<endl;
            if(arr[mid]>x)
                right = mid-1;
            else
                left = mid;
        }

        right = min(len-1,left+k);
        left = max(0,left-k);

        while(right-left+1 > k)
        {
            if( abs(arr[left]-x) > abs(arr[right]-x) )
                left+=1;
            else
                right-=1;
        }
        return vector(arr.begin()+left,arr.begin()+right+1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29