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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-k-closest-elements
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

一、最无脑的解法是优先队列，开辟一个大小为k的优先队列，遍历每一个数计算其和x的差值，看能否入队，最后将队列的k个元素排好序返回就行了。见代码一。

二、双指针的解法也比较好想，可以先用找到最接近x的那个数，然后从这个数往两边扩散找够k个最接近x的。

不过，还有不需要二分的双指针思路，直接使用两个指针从数组两端向中间靠拢，那边更接近x就移动哪边的指针。见代码二。

三、直接二分的思路不太好想，可以看liweiwei的「题解」，主要思路是二分结果数组的左边界，因为长度为k的相邻的两个子数组只有端点处不同，所以可以看做是在k+1的子数组两端选择删除一个元素，就等同于左边界的移动。见代码三。

代码

代码一 优先队列

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(k, (a, b) -> b[1] - a[1]);
        for (int num : arr) {
            int diff = Math.abs(num - x);
            if (minHeap.size() < k) {
                minHeap.offer(new int[]{num, diff});
            } else if (diff < minHeap.peek()[1]) {
                minHeap.poll();
                minHeap.offer(new int[]{num, diff});
            }
        }
        List<Integer> ans = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            ans.add(minHeap.poll()[0]);
        }
        Collections.sort(ans);
        return ans;
    }
}

代码二 双指针

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> ans = new ArrayList<>();
        int n = arr.length;
        int l = 0;
        int r = n - 1;
        int step = n - k;
        while (step > 0) {
            // l指向的数和x差值比r更大，移动l指针
            if (x - arr[l] > arr[r] - x) {
                l++;
            } else {
                // 否则移动r指针，注意等于时移动r，因为题目要求确保差值相同时数字要更小的
                r--;
            }
            step--;
        }
        for (int i = l; i <= r; i++) {
            ans.add(arr[i]);
        }
        return ans;
    }
}

代码三 二分

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int n = arr.length;
        int low = 0;
        int high = n - k;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (x - arr[mid] > arr[mid + k] - x) {
                low = mid + 1;
            } else {
                // 这里同样等于时删除右边的元素，确保差值相同时数字更小
                high = mid;
            }
        }
        List<Integer> res = new ArrayList<>(k);
        for (int i = low; i < low + k; ++i) {
            res.add(arr[i]);
        }
        return res;
    }
}