【排序, 双指针】找到 K 个最接近的元素

题目

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 <= 10^4
• arr 按 升序 排列
• -10^4 <= arr[i], x <= 10^4

解题

方法一：排序

思路

首先把数组按照与 x 的距离越近越靠前的顺序排序，具体来说：

• 如果 $|arr[i] - x|$ 相等，越小的越靠前。
• 否则 $|arr[i] - x|$ 的值越小越靠前。

然后拿出 arr 中前 k 个元素组成一个新的数组后升序排序返回。

代码

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        sort(arr.begin(), arr.end(), [x](int& a, int& b) {
            int diff_a = abs(a - x), diff_b = abs(b - x);
            return diff_a == diff_b ? a < b : diff_a < diff_b;
        });
        sort(arr.begin(), arr.begin() + k);
        return {arr.begin(), arr.begin() + k};
    }
};

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> lst = new ArrayList<Integer>() {{
            for (int num : arr) this.add(num);
        }};
        Collections.sort(lst, (a, b) -> {
            int diffA = Math.abs(a - x), diffB = Math.abs(b - x);
            return diffA == diffB ? a - b : diffA - diffB;
        });
        List<Integer> ans = lst.subList(0, k);
        Collections.sort(ans);
        return ans;
    }
}

方法二：双指针

思路

反向思考，从排序好的数组 arr 中找到最靠近 x 的 k 个数就是**删除最远离 x 的 arr.length - k**个数。

维护两个指针(left, right)分别指向数组左右两边，如果左指针指向的数与 x 的差值比右指针指向的数与 x 的差值大，说明左边更远离 x 把左指针右移表示删除左边的一个数，反之把右指针左移。

最后返回 arr[left:right+1] (这里类似 python 的数组切片，表示 arr 中的 [left, right+1) 区间)。

代码

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int excld = arr.size() - k;
        auto left = arr.begin(), right = arr.end() - 1;
        for (int i = 0; i < excld; ++i) {
            if (x - *left > *right - x) ++left;
            else --right;
        }
        return {left, right + 1};
    }
};

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0, right = arr.length - 1;
        int excld = arr.length - k;
        while (excld-- > 0) {
            if (x - arr[left] > arr[right] - x) ++left;
            else --right;
        }
        List<Integer> ans = new ArrayList<>();
        for (; left <= right; ++left) ans.add(arr[left]);
        return ans;
    }
}