跳至主要內容

658. 找到 K 个最接近的元素


658. 找到 K 个最接近的元素

🟠   🔖  数组 双指针 二分查找 排序 滑动窗口 堆(优先队列)  🔗 力扣open in new window LeetCodeopen in new window

题目

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 ,两个整数 kx ,从数组中找到最靠近 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 = 0right = arr.length - 1
  2. 使用循环逐步收缩窗口,窗口长度 right - left + 1arr.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 = 0right = 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);
};

相关题目

题号标题题解标签难度力扣
374猜数字大小[✓]二分查找 交互🟢🀄️open in new window 🔗open in new window
375猜数字大小 II[✓]数学 动态规划 博弈🟠🀄️open in new window 🔗open in new window
719找出第 K 小的数对距离数组 双指针 二分查找 1+🔴🀄️open in new window 🔗open in new window
2239找到最接近 0 的数字[✓]数组🟢🀄️open in new window 🔗open in new window