658. 找到 K 个最接近的元素
658. 找到 K 个最接近的元素
🟠 🔖 数组
双指针
二分查找
排序
滑动窗口
堆(优先队列)
🔗 力扣
LeetCode
题目
Given a sorted integer array arr
, two integers k
and x
, return the k
closest integers to x
in the array. The result should also be sorted in ascending order.
An integer a
is closer to x
than an integer b
if:
|a - x| < |b - x|
, or|a - x| == |b - x|
anda < b
Example 1:
Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]
Example 2:
Input: arr = [1,1,2,3,4,5], k = 4, x = -1
Output: [1,1,2,3]
Constraints:
1 <= k <= arr.length
1 <= arr.length <= 10^4
arr
is sorted in ascending order.-10^4 <= arr[i], x <= 10^4
题目大意
给定一个 排序好 的数组 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]
提示:
1 <= k <= arr.length
1 <= arr.length <= 10^4
arr
按 升序 排列-10^4 <= arr[i], x <= 10^4
解题思路
思路一:双指针
- 初始化双指针
left = 0
和right = arr.length - 1
。 - 使用循环逐步收缩窗口,窗口长度
right - left + 1
从arr.length
开始逐渐减小到k
。 - 比较窗口两端的数值与目标值
x
的距离:- 如果左端元素更接近
x
,则收缩右端(right--
)。 - 否则,收缩左端(
left++
)。
- 如果左端元素更接近
- 当窗口的长度缩减为
k
时,窗口中的元素即为答案。 - 最终返回
arr[left:right+1]
,即当前窗口中的元素。
复杂度分析
- 时间复杂度:
O(n)
- 收缩窗口需要遍历最多
n − k
次,复杂度为O(n - k)
。 slice
方法截取子数组的复杂度为O(k)
。- 总时间复杂度为
O(n)
。
- 收缩窗口需要遍历最多
- 空间复杂度:
O(1)
,使用了常数个额外变量。
思路二:二分查找
因为最终答案是一个长度为 k
的连续子数组 arr[left:left + k]
,所以我们只需要找到这个子数组的 左边界 left
。
初始化
left = 0
,right = arr.length - k
。- 注意
right
的初始值为arr.length - k
,因为窗口大小固定为k
,我们最多可以将窗口的起始位置设置为arr.length - k
。
- 注意
每次计算中点
mid
,比较以mid
开头的子数组和以mid + 1
开头的子数组哪个更接近x
。具体来说,比较
x - arr[mid]
(左侧的距离)和arr[mid + k] - x
(右侧的距离):- 如果
x - arr[mid] > arr[mid + k] - x
,说明右侧的子数组更接近x
,需要把left
向右移动,即left = mid + 1
。 - 否则,左侧的子数组更接近
x
,需要把right
向左移动,即right = mid
。
- 如果
二分查找的终止条件:当
left == right
时,left
即为最终的左边界。返回结果:子数组即为
arr[left:left + k]
。
复杂度分析
时间复杂度:
O(log(n - k) + k)
- 二分查找每次迭代将范围减半,最多需要
O(log(n - k))
次比较。 slice
方法截取子数组的复杂度为O(k)
。- 总复杂度为
O(log(n - k) + k)
。
- 二分查找每次迭代将范围减半,最多需要
空间复杂度:
O(1)
,仅使用了常量空间。
代码
/**
* @param {number[]} arr
* @param {number} k
* @param {number} x
* @return {number[]}
*/
var findClosestElements = function (arr, k, x) {
let left = 0,
right = arr.length - 1;
// 收缩窗口直到窗口大小为 k
while (right - left >= k) {
if (Math.abs(arr[left] - x) <= Math.abs(arr[right] - x)) {
right--; // 收紧右端
} else {
left++; // 收紧左端
}
}
// 返回窗口中的元素
return arr.slice(left, right + 1);
};
/**
* @param {number[]} arr
* @param {number} k
* @param {number} x
* @return {number[]}
*/
var findClosestElements = function (arr, k, x) {
let left = 0,
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; // 舍弃右半部分
}
}
// 返回以 left 为起点的 k 个元素
return arr.slice(left, left + k);
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
374 | 猜数字大小 | [✓] | 二分查找 交互 | 🟢 | 🀄️ 🔗 |
375 | 猜数字大小 II | [✓] | 数学 动态规划 博弈 | 🟠 | 🀄️ 🔗 |
719 | 找出第 K 小的数对距离 | 数组 双指针 二分查找 1+ | 🔴 | 🀄️ 🔗 | |
2239 | 找到最接近 0 的数字 | [✓] | 数组 | 🟢 | 🀄️ 🔗 |