LEETCODE 658. Find K Closest Elements 解题思路分析

题目大意：

找到 K 个最接近的元素

给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样，优先选择数值较小的那个数。

示例 1:

输入: [1,2,3,4,5], k=4, x=3
输出: [1,2,3,4]

示例 2:

输入: [1,2,3,4,5], k=4, x=-1
输出: [1,2,3,4]

说明:

1. k 的值为正数，且总是小于给定排序数组的长度。
2. 数组不为空，且长度不超过 10⁴
3. 数组里的每个元素与 x 的绝对值不超过 10⁴

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=658

解题思路分析：

题目要求求出一组数字，它们是与某个数字最为接近的一组数字。简单来讲，我们需要先找到最接近x的数字n，最后的结果一定是数组中包含数字n的一个子数组。我们需要做的是不断地比较n两边的数字的同时，不断的扩大n两边的范围，直到范围长度等于k为止。

解题时，首先我们考虑最接近数字x的数字肯定是x本身，但是题目给定的数组中不一定包含这个数字，这就为我们寻找目标增加了难度。不过我们可以变换一下思路，我们可以先求出数组中第一个小于等于x的数字L（这个方法我们在讲解二分查找算法时，非常详细的总结过：LEETCODE常见算法之二分查找超详细白话讲解），该数字L有可能等于x，也可能是小于x并且最接近x的数字。另外，由于L是第一个小于等于x的数字，因此，与L所在的下标右侧相邻一位的数字R一定大于x并且最接近x的一个数字，L和R两个数字与x差值更小的一方一定是最接近x的数字。举个例子，比如数组：

arr = [2, 2, 10, 10]; 
x = 9;

数组中第一个小于等于9的是下标为1的数字2，而它的右侧相邻一位是下标为2的数字10，显然10是最接近9的数字。

找到最小数字之后，我们还需要找到次小数字（一共找到k个），这时，如果最小数字是R，那么我们将R所在的下标加一，反之，将L所在的下标减一，继续比较L和R谁更接近x，重复以上步骤，直到找出k个元素为止。另外，解题时需要注意L和R所在下标不能越界，当一方越界时，我们只能从没有越界的一方中取最接近x的值。

实现代码：

public List<Integer> findClosestElements(int[] arr, int k, int x) {
    // 返回结果
    List<Integer> res=new ArrayList<>();
    // 找到第一个小于等于x的数字
    int left=findFirstSmallOrEqual(arr,x);
    // 第一个大于x的数字
    int right=left+1;
    // 找到k个最接近x的数字
    while(k>0){
        // 如果左指针越界，右指针指向的数字是最接近x的
        // 将右指针指向的数字划入结果范围，右指针加一
        if(left<0) right++;
        // 如果右指针越界，左指针指向的数字是最接近x的
        // 将左指针指向的数字划入结果范围，左指针减一
        else if(right>=arr.length) left--;
        else{ // 两指针都没有越界
            // 如果左指针指向的数字与x的差值小于等于右指针与x的差值
            if((x-arr[left])<=(arr[right]-x)){
                // 将左指针指向的数字划入结果范围，左指针减一
                left--;
            }else{
                // 反之将右指针指向的数字划入结果范围，右指针加一
                right++;
            }
        }
        k--;
    }
    // 由于左右指针都多进行了一次加一减一操作，还原指针
    left++;
    right--;
    // 将区间内的数字加入返回结果
    for(int i=left;i<=right;i++){
        res.add(arr[i]);
    }
    return res;
}
// 二分查找
int findFirstSmallOrEqual(int[] arr, int x){
    int low=0,high=arr.length-1;
    while(low<=high){
        int mid=(low+high)/2;
        if(arr[mid]<=x) low=mid+1;
        else high=mid-1;
    }
    return high>=0?high:0;
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 98.65% of Java online submissions for Find K Closest Elements.

Memory Usage: 43.2 MB, less than 5.88% of Java online submissions for Find K Closest Elements.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-658-find-k-closest-elements-解题思路分析/