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]

解题思路

1.排除法（双指针）

我们可以反向来思考这道题，即删去n-k个最不接近的元素，剩下的元素即为最接近的k个。

我们设置指向头尾的两个指针left，right，每次删除掉相差更远的元素，对应指针向内缩减。

时间复杂度为$O(n)$

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


    }
}

这里两数之差的比较没有采用绝对值，而是x - arr[left] <= arr[right] - x，一种比较容易理解的方法是 x <= (arr[left] + arr[right]) / 2;

2.二分查找

我们要找最接近的k个数，当我们找到最优区间的最左边的那个数时，问题也相应解决。

这最优区间的最左边的数只会存在于区间 [0， n - k]。就可以通过二分查找在这区间中找到答案，设这个值为target。

令left = 0， right=n-k，二分mid=（left + right）/ 2, 二分的手段可以认为是一种随机选取，目的是通过二分可以快速排除不可能存在target的区间。

关键在于每次的判断条件，我们考虑 [mid, mid+k]这个k+1的区间，因为是k+1个数，我们必能够排除一个相对于x更远的数，同解法一类似，若arr[mid + k]与x更接近，则删除最左端也就是mid所指的数，因此mid及mid左边的数不可能是最优左边界（target），令left = mid + 1; 相反,则要删除最右端的数，导致的结果是mid的右边都不可能是target，令right = mid。通过这种判断手段，来在可能区间中定位target。

时间复杂度$O(logn + k)$

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