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| and a < 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

解题思路

思路一：双指针

1. 初始化双指针 left = 0 和 right = arr.length - 1。
2. 使用循环逐步收缩窗口，窗口长度 right - left + 1 从 arr.length 开始逐渐减小到 k。
3. 比较窗口两端的数值与目标值 x 的距离：
   • 如果左端元素更接近 x，则收缩右端（right--）。
   • 否则，收缩左端（left++）。
4. 当窗口的长度缩减为 k 时，窗口中的元素即为答案。
5. 最终返回 arr[left:right+1]，即当前窗口中的元素。

复杂度分析

• 时间复杂度：O(n)
  • 收缩窗口需要遍历最多 n − k 次，复杂度为 O(n - k)。
  • slice 方法截取子数组的复杂度为 O(k)。
  • 总时间复杂度为 O(n)。
• 空间复杂度：O(1)，使用了常数个额外变量。

思路二：二分查找

因为最终答案是一个长度为 k 的连续子数组 arr[left:left + k]，所以我们只需要找到这个子数组的 左边界 left。

1. 初始化 left = 0，right = arr.length - k。

   • 注意 right 的初始值为 arr.length - k，因为窗口大小固定为 k，我们最多可以将窗口的起始位置设置为 arr.length - k。

2. 每次计算中点 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。

3. 二分查找的终止条件：当 left == right 时，left 即为最终的左边界。

4. 返回结果：子数组即为 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 的数字	[✓]	数组	🟢	🀄️ 🔗