题目
给定一个排序好的数组,两个整数 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]
说明:
- k 的值为正数,且总是小于给定排序数组的长度。
- 数组不为空,且长度不超过 104
- 数组里的每个元素与 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]