658. 找到 K 个最接近的元素 Medium
给定一个 排序好 的数组 arr
,两个整数 k
和 x
,从数组中找到最靠近 x
(两数之差最小)的 k
个数。返回的结果必须要是按升序排好的。
整数 a
比整数 b
更接近 x
需要满足:
|a - x| < |b - x|
或者
|a - x| == |b - x|
且 a < b
示例 1:
输入:arr = [1,2,3,4,5], k = 4, x = 3
输出:[1,2,3,4]
示例 2:
输入:arr = [1,1,2,3,4,5], k = 4, x = -1
输出:[1,1,2,3]
解题思路
输入: 一个排好序数组 arr
,两个整数 k 和 x
输出: 返回 k 个最接近 x 的子数组
本题属于典型的二分 + 滑动窗口问题。
这道题看似是滑动窗口类型,但是由于是有序的数组所以我们可以借助二分快速找到窗口的左边界
我们可以先设定好其实窗口范围 [0, len(arr) - k]
通过二分找到 mid 判断 x - arr[mid] 是否大于 arr[mid + k] - x
假如大于则说明 mid
这个位置还是距离 x
比较远,左边界肯定在 mid
右侧,我们移动左端口到 mid + 1
假如小于等与则说明 mid
这个位置离 x
比较近,左边界可能在 mid
或者 mid
左侧,我们可以继续缩小范围到 [left, mid]
中在找更接近窗口左边界的位置
最后 left
就是左边界起点,我们直接返回 [left, left + k]
这个区间的数组
代码实现
python
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
# 设定窗口起点的二分查找范围:从 0 到 len(arr) - k
# 因为窗口长度固定为 k,起点最大只能是 len(arr) - k
left, right = 0, len(arr) - k
while left < right:
mid = (left + right) // 2 # 当前窗口起点
# 比较窗口两边端点离 x 的距离,决定窗口往哪边移
# 如果左边 arr[mid] 更远(离 x 更远),就向右移动窗口
# 否则,保留当前 mid 或往左试试更好的
if x - arr[mid] > arr[mid + k] - x:
left = mid + 1
else:
right = mid
# 最终窗口起点就是 left,对应的连续 k 个数即为答案
return arr[left:left + k]
javascript
/**
* @param {number[]} arr
* @param {number} k
* @param {number} x
* @return {number[]}
*/
var findClosestElements = function(arr, k, x) {
let left = 0;
let right = arr.length - k;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (x - arr[mid] > arr[mid + k] - x) {
left = mid + 1;
} else {
right = mid;
}
}
return arr.slice(left, left + k);
};
复杂度分析
时间复杂度:O(log n)
空间复杂度:O(1)