658. 找到 K 个最接近的元素


title: 找到K个最接近的元素
date: {{ date }}
categories: 算法题

tags: 二分搜索

找到K个最接近的元素

给定一个排序好的数组,两个整数 kx,从数组中找到最靠近 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

更新(2017/9/19):
这个参数 arr 已经被改变为一个整数数组(而不是整数列表)。 请重新加载代码定义以获取最新更改。


思路

本文参考这位大佬的题解[方法二: 二分查找最优区间的左边界]

https://leetcode-cn.com/problems/find-k-closest-elements/solution/pai-chu-fa-shuang-zhi-zhen-er-fen-fa-python-dai-ma/

此问题转换为 查找最优区间的左边界

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

例如这个示例,k为4,即区间的长度为4,这个区间可能是 [1,2,3,4] 和 [2,3,4,5],所以最左边界元素的区间在 [0, 1]范围内

也就是说,最优区间的左边界[0, length-k]这个区间中

那么,现在的问题就转换成了 在[0, length-k]区间内找到一个元素,这个元素是最优区间的左边界

来整理一下题目的条件:

x : 目标值

k : 结果数组内的元素个数

  1. 最优区间内的每个元素与 x 的差值都是最小的
  2. 找到的最优区间必须升序排列的

步骤解析

1.找到左边界元素所在区间

这个很简单,就是[0, length-k]

2.区间内的中位数(x - arr[mid]arr[mid+k] - x进行比较)

首先明白此时midmid+k各自代表的意义是什么?

mid:“最优区间”的左边界,可能当前不是最优区间,待进一步二分查找

mid+k:“最优区间”右边界的右边一位

1) 如果x - arr[mid] > arr[mid+k] - x,说明什么?

  • 说明 x 更应该靠近arr[mid+k]一些, 即arr[mid, mid+k]这个区间整体向右滑动,才可能成为 最优区间
  • 要使得这个区间向右滑动,也就是将这个区间的左边界右移
  • 回到二分查找,就是向右收缩 => left = mid + 1

2) 如果x - arr[mid] < arr[mid+k] - x,说明什么?

  • 说明 mid + k位置 及 右边所有的元素 都不符合最优区间(因为是升序的),当前的“最优区间”为 arr[mid, mid + k]。但是mid之前可能存在有元素哦,所以mid之前的元素应该继续进行判断
  • mid之前的元素可能有更优的,就是区间可能向左移动,也可能当前mid就是最优区间的左边界(不移动)
  • 为了找到更合适的mid,所以应该收缩[0, length-k]这个区间,因为是去找mid及mid之前的元素,所以是向左收缩,即 right = mid
  • 为什么是right = mid,而不是right = mid - 1?因为mid这个位置的值,可能刚好就是最优区间的左边界,如果mid-1就错过了

3) 如果x - arr[mid] = arr[mid+k] - x,说明什么?

  • 仔细想想,这两者差值相等的情况是和 2) 的情况一致

3.经过左右边界的不断收缩,最终找到的一个元素,这个元素就是 最优区间的左边界,即可求出答案

程序执行动图

代码

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        left, right = 0, len(arr) - k # 确定最优区间的左边界所在区间范围
        while left < right:
            mid = (left + right) >> 1 # 找到中位数
            if x - arr[mid] > arr[mid+k] - x: # 比较差值,收缩区间
                left = mid + 1
            elif x - arr[mid] <= arr[mid+k] - x:
                right = mid
        return arr[left:left+k]
仅有 1 条评论
  1. Leonrad Garcia Leonrad Garcia

    Hi, this is Leonrad.

    Today I have good news for you, witch you can get $30 free bonus in a minute.

    All you have to do is to register Vera & John online casino link below and that's it.
    You can register by free e-mail and no need kyc.

    Registration form
    https://www3.samuraiclick.com/go?m=28940&c=34&b=926&l=1

    After you get your free bonus, play casino and make money!
    Many people sent me thanks mail because they won more than $2,000-$10,000
    by trusting me.

    Don’t miss this chance and don't for get that your chance is just infront of you.
    Get free bonus and win your life!

    You can with draw your prize by Bitcoin, so If you need best crypto debit card, try Hcard.
    https://bit.ly/31zTBD0

    It is Mastercard brand and you can exchange your crypto by Apps.
    Hcard cost you $350 + shipping, but it will definitely worth.

    This is how rich people always get their profits.
    So, if you wanna win your life for free, do not miss your last chance.

    Thank you
    Leonrad Garcia.

添加新评论