658. 找到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 已经被改变为一个整数数组(而不是整数列表)。 请重新加载代码定义以获取最新更改。


思路

一个月前做过此题,今天又做了下,不出意外的又不知道怎么写了

回来看这篇文章,写得也不是特别清晰,所以又重写了这篇题解

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

我看了大佬们的题解,都讲到了此问题转换为查找最优区间的左边界

这里,我说明下为什么可以转换成查找最优区间的左边界的问题

转换问题

对我个人而言,我一定需要去理解这个为什么,否则后面做题总是会混乱

k表示的是 最后输出的区间长度,也就是最优区间的长度

那么可以理解为,只要确定一个区间的第一个元素就确定了这个区间,即 [m ... m + k]

所以问题就可以转换成寻找区间的左边界

因为k值 和 nums数组长度都是固定,所以nums能够产生的长度为k的子区间个数也是确定的

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

例如上方示例,k为4,最优子区间只能是 [1,2,3,4] 或者 [2,3,4,5],所以子区间的左边界元素在 **[0, 1]**范围内

换成表达式,最优子区间的左边界在[0, length - k]

那么现在就是在[0, length - k]范围内寻找一个元素

如何比较

在二分查找算法中,就是通过每一轮的条件比较,丢掉一半无用的数据

在每一轮的循环中,我们可以计算出x - nums[mid] 的差值,如果这个差值过大,肯定需要向右移动,差值过小则向左移动。

那么如何判断这个差值是过大还是过小呢? 和谁比较呢?

与下一个子区间的左边界元素比较

  • 如果x - nums[mid] > nums[mid + k] - x

此时区间[mid ... mid + k - 1] 应该整体向后移动一位变成 [mid + 1 ... mid + k], 为什么?

1、这个数组是升序排列;

2、找到了差值更小值,所以应该将更小的值给包含到区间内,而k的长度不变,所以整体向右移动一位,其实就是子区间左边界向右移动一位

  • 如果x - nums[mid] < nums[mid + k] - x

这样的情况,说明[mid + k ... right]都不会是我们所需要的了,下一轮的搜索区间就是[left, mid],因为mid这个位置可能刚好就是答案,所以这里向左收缩至mid即可,不必到mid - 1

  • 如果x - nums[mid] == nums[mid + k] - x

题目要求:如果有两个数与 x 的差值一样,优先选择数值较小的那个数。

所以等于 和 小于的处理方法一样

代码

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]