找到 K 个最接近的元素

问题描述

来源：LeetCode第658题

难度：中等

给定一个排序好的数组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的k个数字，最简单的一种解决方式就是使用双指针，一个指向数组第一个元素，一个指向数组的最后一个元素。然后比较他俩的值，哪个和x相减的绝对值大，哪个就往中间移一步，如下图所示。

代码如下

public List<Integer> findClosestElements(int[] arr, int k, int x) {
    int left = 0;// 左指针
    int right = arr.length - 1;// 右指针
    int removeCount = arr.length - k;//需要移除元素的个数
    while (removeCount-- > 0) {
        if (x - arr[left] <= arr[right] - x)
            right--;
        else
            left++;
    }

    // 返回剩下的k个元素即可
    List<Integer> res = new ArrayList<>();
    for (int i = left; i <= right; i++)
        res.add(arr[i]);
    return res;
}

解法二

除了上面的解决方式以外，我们还可以使用滑动窗口，因为数组是有序的，所以我们可以通过二分法来查找x在数组中的位置，如果数组中没有x，我们返回x如果放到数组中，应该存放的位置。

然后以这个位置来确定窗口的大小为k，窗口确定之后我们只需要根据窗口左边和右边值来判断窗口是否往右移动，原理也比较简单，我们来看下代码。

public List<Integer> findClosestElements(int[] arr, int k, int x) {
    // 确定x在数组中的下标，如果数组中没有arr，
    // 则返回x放到数组中应该存放的位置
    int index = binarySearch(arr, x);
    // 确定窗口的大小
    int left = Math.max(0, index - k); // 窗口的左边界
    int right = left + k - 1; // 窗口的右边界
    // 比较窗口的左右两个边界，确定窗口是否需要往右边滑动
    while (right < arr.length - 1 && x - arr[left] > arr[right + 1] - x) {
        left++;
        right++;
    }

    // 把窗口中的元素放到集合中
    List<Integer> res = new ArrayList<>();
    for (int i = left; i <= right; i++)
        res.add(arr[i]);
    return res;
}

// 二分法查找
private int binarySearch(int[] array, int x) {
    int left = 0;
    int right = array.length - 1;
    while (left <= right) {
        int mid = (left + right) >>> 1;
        int midVal = array[mid];
        if (midVal < x)
            left = mid + 1;
        else if (midVal > x)
            right = mid - 1;
        else
            return mid;
    }
    return left;
}