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. 数组不为空,且长度不超过 104
  3. 数组里的每个元素与 x 的绝对值不超过 104

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: 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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。