中等

问题描述

给定一个 排序好 的数组 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,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]

提示：

• 1 <= k <= arr.length
• 1 <= arr.length <= 104
• arr 按 升序 排列
• 104 <= arr[i], x <= 104

排序

将数组按更接近 $x$ 的规则进行排序，排序后截取前 $k$ 个数，再将截取出的数据从小到大排序即可。

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findClosestElements = function (arr, k, x) {
  return arr
    .sort((a, b) => {
      const d1 = Math.abs(a - x)
      const d2 = Math.abs(b - x)
      if (d1 !== d2) {
        return d1 - d2
      } else {
        return a - b
      }
    })
    .slice(0, k)
    .sort((a, b) => a - b)
}

• 时间复杂度：$O(n\log{n})$
• 空间复杂度：$O(\log{n})$

二分查找 + 双指针

使用二分查找找出小于等于 $x$ 的最大下标 $idx$，然后以 $idx$ 为右端，$idx - 1$ 为左端，向左右扩散 $k$ 次，最终对数组进行截取。

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findClosestElements = function (arr, k, x) {
  const n = arr.length
  let l = 0
  let r = n - 1
  while (l < r) {
    const mid = (l + r) >> 1
    if (arr[mid] === x) {
      l = mid
      break
    } else if (arr[mid] < x) {
      l = mid + 1
    } else {
      r = mid
    }
  }
  r = l--
  while (k-- > 0) {
    if (l < 0) {
      r++
    } else if (r >= n) {
      l--
    } else if (x - arr[l] <= arr[r] - x) {
      l--
    } else {
      r++
    }
  }
  return arr.slice(l + 1, r)
}

• 时间复杂度：$O(\log{n} + k)$
• 空间复杂度：$O(1)$