更新题目 658. Find K Closest Elements

题目 lc658 · 修改（rev 2） · cc · 2026-10-27 00:34
body

@@ -1,25 +1,78 @@
 ## 题目
 
-在有序数组 `arr` 中找出离 `x` 最近的 `k` 个数，按升序返回；距离相同时取较小的数。
+给一个升序数组 `arr`、整数 `k` 和 `x`，找出 `arr` 里离 `x` 最近的 `k` 个数，按升序返回。数 `a` 比数 `b` 离 `x` 更近，指 $|a - x| < |b - x|$，或者 $|a - x| = |b - x|$ 且 $a < b$。也就是说距离相同时取较小的数。题目保证 $1 \le k \le n$（`n` 是数组长度），`x` 不一定在数组里，可以比所有元素都小或都大。
+
+例子：`arr = [1, 2, 3, 4, 5]`，`k = 4`，`x = 3`，答案是 `[1, 2, 3, 4]`。`1` 和 `5` 到 `3` 的距离都是 2，按规则留下较小的 `1`。
 
 [LeetCode 原题](https://leetcode.com/problems/find-k-closest-elements/)
 
+## 面经里怎么考的
+
+Visa Senior Software Engineer 的 VO 第二轮，这一轮是 project 讨论加 coding，coding 部分出的是这道原题，面试官提示用二分。所以面试时要能直接写出下面「二分找窗口左端点」的做法，并说清楚比较条件为什么单调。
+
 ## 思路
 
-答案一定是数组里一段长度为 `k` 的连续窗口，所以问题变成找窗口的左端点 `L`，范围是 `[0, n - k]`。比较窗口 `[L, L + k - 1]` 和右移一格后的窗口 `[L + 1, L + k]`，它们只差 `arr[L]` 和 `arr[L + k]` 两个元素。如果 `x - arr[L] <= arr[L + k] - x`，说明左端的元素不比右端新加入的更远，窗口不应该再右移，答案在 `L` 或它左边；否则答案在 `L` 右边。这个判断从左到右是前假后真的，所以可以套模板找第一个满足的 `L`。
+最直接的做法是把所有数按 `(abs(a - x), a)`（先比到 `x` 的距离，再比数值）排序后取前 `k` 个，再排回升序，时间 $O(n \log n)$，没用上数组有序这一点。
 
-## 步骤
+数组有序时，答案一定是一段长度为 `k` 的连续窗口：离 `x` 最近的那批数挨在一起，中间不会跳过一个更远的数。于是问题变成找窗口的左端点 `L`，取值范围是 $[0, n - k]$。
 
-1. 设 `lo = 0`，`hi = n - k`，左端点最大是 `n - k`，这个位置不用比较，当作已知满足。
-2. `while lo < hi:` 取 `mid = (lo + hi) // 2`，此时 `mid + k <= n - 1`，不会越界。
-3. 如果 `x - arr[mid] <= arr[mid + k] - x`，令 `hi = mid`，否则令 `lo = mid + 1`。
-4. 返回 `arr[lo : lo + k]`。
+关键一步是比较窗口 `[L, L + k - 1]` 和右移一格后的窗口 `[L + 1, L + k]`。两者只差两个元素：右移会去掉 `arr[L]`、加进 `arr[L + k]`。判断条件写成
+
+$$
+x - arr[L] \le arr[L + k] - x
+$$
+
+条件成立时，`arr[L]` 不比 `arr[L + k]` 远（距离相等时 `arr[L]` 是较小的那个，按规则也该留下），右移没有好处。条件不成立时，右移一格不会变差，分两种情况：
+
+- `arr[L + k]` 严格更近，窗口 `L + 1` 比窗口 `L` 好。
+- `arr[L]` 和 `arr[L + k]` 是同一个值、都在 `x` 左边（比如两个都是 `2`、`x = 3`）。两个窗口装的数完全一样，右移不会变差。
+
+这个条件能二分，是因为它从左到右先是一段不成立、后是一段成立。把条件移项得到 $arr[L] + arr[L + k] \ge 2x$。数组升序，`L` 增大时 $arr[L] + arr[L + k]$ 不会变小，所以条件一旦在某个 `L` 成立，对更大的 `L` 也都成立。答案就是第一个让条件成立的 `L`，记作 `L*`。`L*` 左边的每个窗口都不比右边一格的好，一路右移到 `L*` 不会变差。从 `L*` 往右，每右移一格都不会变好。
+
+条件里用的是带符号的差，不加绝对值，单调性靠的就是这一点。写成 `abs(x - arr[L]) <= abs(arr[L + k] - x)` 时，两端都在 `x` 左边且值相同会判成立，再往右又判不成立，条件不再单调。`arr = [1, 1, 2, 2, 2, 2, 2, 3, 3]`、`k = 3`、`x = 3` 时，`L` 从 0 到 5 的 `abs` 条件依次是「否、否、是、是、否、否」。二分第一次取 `mid = 3`，判成立，就把 `L = 4` 到 `6` 全扔掉了，而正确答案 `[2, 3, 3]` 在 `L = 6`。最后返回的是 `L = 2` 的 `[2, 2, 2]`。带符号的写法在 `arr[L + k] < x` 时右边 $arr[L + k] - x < 0 \le x - arr[L]$，一定判不成立，窗口继续右移。
+
+`L = n - k` 时 `arr[L + k]` 越界，没法比较。这个位置不用比，直接当作条件成立：窗口不能再往右了，它是兜底的答案。
+
+> [!say] The answer is always a contiguous window of size k, so I binary search for its left end. Window L and window L plus one differ only in arr[L] and arr[L plus k]. I check whether x minus arr[L] is at most arr[L plus k] minus x. With signed differences the check is false and then true as L grows, so binary search works. With absolute values it stops being monotonic.
+
+## 代码
+
+```python
+from typing import List
+
+
+def find_closest_elements(arr: List[int], k: int, x: int) -> List[int]:
+    """返回 arr 中离 x 最近的 k 个数（升序），距离相同取较小的数。"""
+    lo, hi = 0, len(arr) - k          # 窗口左端点的取值范围是 [0, n - k]
+    while lo < hi:
+        mid = (lo + hi) // 2          # mid < hi <= n - k，所以 mid + k <= n - 1
+        if x - arr[mid] <= arr[mid + k] - x:
+            hi = mid                  # 左端的 arr[mid] 不比 arr[mid + k] 远，窗口不该右移
+        else:
+            lo = mid + 1              # 右移一格不会变差，窗口至少要右移一格
+    return arr[lo:lo + k]
+```
+
+`hi` 从 `n - k` 开始、循环条件是 `lo < hi`，所以 `mid` 最大是 `n - k - 1`，`arr[mid + k]` 不会越界。`k == n` 时 `hi = 0`，不进循环，直接返回整个数组。
+
+2026-10-27 在云端用 Python 3 跑过两项：
+
+- 上面的函数和暴力解（按 `(abs(a - x), a)` 排序取前 `k` 个，再排回升序）对拍 10 万组随机输入（`random.seed(20261027)`，每组依次抽 `n`、`k`、`n` 个元素（排序）、`x`，`n` 取 1 到 10，`k` 取 1 到 `n`，元素和 `x` 取 -7 到 7 的整数），全部一致。同一批输入上，`abs` 版错 1044 组，把 `<=` 写成 `<` 的版本错 6254 组。
+
+正确版和「易错点」里的三个错误写法，在下面三组输入上并排跑的结果：
+
+| 输入 `(arr, k, x)` | 正确答案 | 正确版 | `abs` 版 | `<` 版 | `hi = n - 1` 版 |
+| --- | --- | --- | --- | --- | --- |
+| `[1,2,3,4,5], 4, 3` | `[1,2,3,4]` | `[1,2,3,4]` | `[1,2,3,4]` | `[2,3,4,5]` | `IndexError` |
+| `[1,1,2,2,2,2,2,3,3], 3, 3` | `[2,3,3]` | `[2,3,3]` | `[2,2,2]` | `[2,3,3]` | `IndexError` |
+| `[1,2,3,4,5], 2, 10` | `[4,5]` | `[4,5]` | `[4,5]` | `[4,5]` | `IndexError` |
+
+## 复杂度
+
+二分在 $n - k + 1$ 个左端点里找，比较 $O(\log(n - k))$ 次，切出结果要 $O(k)$，总时间 $O(\log(n - k) + k)$。除了返回的结果，额外空间 $O(1)$。
 
 ## 易错点
 
-- 不要给两边加 `abs`。当 `arr[mid]` 和 `arr[mid + k]` 都在 `x` 的同一侧时，带绝对值的比较会给出相反的结论，比如 `arr = [1,1,2,2,2,2,2,3,3]`、`x = 3`、`k = 3` 时会出错。不加绝对值的写法本质是在比较两端到 `x` 的有向距离，始终单调。
-- 相等时要选择 `hi = mid`（保留左边），因为题目规定距离相同取较小的数。
-
-## 复杂度
-
-时间 O(log(n - k) + k)，二分找左端点再切出 k 个元素；空间 O(1)，不计结果。
+- **给两边加 `abs`**：条件不再单调，二分会扔掉含答案的那一半，见「思路」里讲带符号差的那一段。
+- **把 `<=` 写成 `<`**：距离相等时丢掉较小的 `arr[mid]`，违反「距离相同取较小的数」，`[1,2,3,4,5]`、`k = 4`、`x = 3` 会返回 `[2,3,4,5]`。
+- **`hi` 设成 `n - 1`**：左端点最大只能是 `n - k`，`hi` 设大了 `arr[mid + k]` 会越界，见「思路」最后一段。
更新题目 658. Find K Closest Elements

body

meta
