找到 K 个最接近的元素 图解题解

这道题到底在问什么

arr

[1,2,3,4,5]

k, x

k=4, x=3

输出

[1,2,3,4]

最优解：一步一步想明白

1. 3数组有序，离 x 最近的 k 个数一定挨在一起。左端点 lo 的范围只有 [0, n−k](再大窗口就出界)，在这上面二分，O(log n) 就能锁定。
2. 4arr[mid] 是窗口左端外那个数、arr[mid+k] 是右端外那个数。左端外更远 → 丢左端，lo=mid+1；否则 hi=mid(相等也走这支，保留更小的数)。下面盯住 lo/hi/mid 三根指针怎么动。
3. 5lo=0, hi=n−k=8换个大点的例子看二分怎么收缩：arr=[1..11]（11 个数），k=3，x=8。lo 指下标 0、hi 指下标 8，答案左端点就夹在这两根指针之间。
4. 6mid = (0+8)/2 = 4mid 落在 lo 和 hi 正中间，下标 4。接下来把以 mid 为左端的窗口 [4,6] 画出来比一比。
5. 7窗口 = arr[mid .. mid+k−1]紫底就是设想的窗口 [4,6]，里头是 5、6、7。现在看窗口两侧外面那两个数离 x=8 谁更远。
6. 8左端外 arr[4]=5 差3 ┆ 右端外 arr[7]=8 差0左端外 arr[4]=5 离 8 差 3(标灰=不划算)，右端外 arr[7]=8 正好差 0。左端更远，保留它不划算——该丢左端、把窗口右移。
7. 9排除下标 0~4，lo → 5lo 跳到 5，下标 0~4 整段变灰出局——左端点不可能再落在那里了。范围一下砍掉一半，缩成 [5,8]。
8. 10mid = (5+8)/2 = 6在新范围 [5,8] 里重新取中点，mid 落到下标 6。再画出以它为左端的窗口。
9. 11窗口 = arr[6 .. 8]新设想窗口 [6,8]，里头是 7、8、9。同样看两侧外面哪个离 x=8 更远。
10. 12左端外 arr[6]=7 差1 ┆ 右端外 arr[9]=10 差2左端外 arr[6]=7 差 1，右端外 arr[9]=10 差 2(标灰=不划算)。右端更远，丢右端、窗口左移。
11. 13排除下标 7~8，hi → 6hi 收到 6，下标 7、8 变灰出局。注意丢右端用 hi=mid(不是 mid−1)，因为 mid 本身可能就是答案左端。范围缩成 [5,6]。
12. 14mid = (5+6)/2 = 5范围只剩 [5,6]，mid 取到下标 5。最后一轮，先把以它为左端的窗口画出来。
13. 15窗口 = arr[5 .. 7]紫底窗口 [5,7]，里头是 6、7、8。最后比一次两侧外面谁离 x=8 更远。
14. 16左端外 arr[5]=6 差2 ┆ 右端外 arr[8]=9 差1左端外 arr[5]=6 差 2(标灰)，右端外 arr[8]=9 只差 1。这回是左端更远，丢左端、lo=mid+1=6。
15. 17排除下标 5，lo → 6lo 跳到 6，下标 5 变灰出局。现在 lo 和 hi 都指向 6，下一步它们就要撞上了。
16. 18lo == hi，停！左端点 = 6lo 和 hi 撞到一起，二分停下。最优窗口左端点就是 6，所有非答案下标都已变灰，11 个数只用 3 轮比较就定下来了。
17. 19两端外侧都比窗口内远停之前再确认一眼：窗口 [6,8] 两侧外面 arr[5]=6 和 arr[9]=10 离 8 都差 2，都不如窗口里的近，再怎么挪都不会更优——这就是二分停在这里的底气。
18. 20从 lo=6 起点亮第 1 格锁定左端点后，从下标 6 起一格一格往右取。先点亮第 1 格 arr[6]=7。
19. 21点亮第 2 格第 2 格 arr[7]=8 点亮——它正好就是 x 本身，离自己距离 0，当然在答案里。
20. 22arr[6..8] = [7,8,9]点亮第 3 格 arr[8]=9，凑满 k=3 个：7、8、9，正好是离 8 最近的三个数，本来就是升序，直接返回。
21. 23arr=[1..5], k=4, x=3 → [1,2,3,4]用同一招跑题目原例 arr=[1,2,3,4,5]：hi=n−k=1，mid=0 时两侧差打平，按规则走 else 保留更小的数，lo=0，取 arr[0..3] = [1,2,3,4]，和答案一致。
22. 27x−arr[mid]==arr[mid+k]−x → 走 else原例里 mid=0 时两侧差都是 2(打平)。规则要求平局取更小的数，所以走 else (hi=mid)，保留靠左的窗口 [1,2,3,4]。若误用 ≥ 让 lo 右移，就会丢掉更小的 1，答案就错了。
23. 29凡是「在有序数组里挑一段固定长度、让它最优」的题都可往这个模板靠。另有双指针从两头往里夹的写法(每次缩离 x 更远的端点)，思路直观但要缩 n−k 次，是 O(n−k)，n 大时不如二分。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def findClosestElements(self, arr, k, x):
        lo, hi = 0, len(arr) - k      # 左端点范围 [0, n-k]
        while lo < hi:
            mid = (lo + hi) // 2
            # 左端外更远 → 丢左端，窗口右移
            if x - arr[mid] > arr[mid + k] - x:
                lo = mid + 1
            else:                     # 否则窗口左移
                hi = mid
        return arr[lo:lo + k]

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int lo = 0, hi = (int)arr.size() - k;   // [0, n-k]
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (x - arr[mid] > arr[mid + k] - x)
                lo = mid + 1;                   // 右移
            else
                hi = mid;                       // 左移
        }
        return vector<int>(arr.begin() + lo, arr.begin() + lo + k);
    }
};

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int lo = 0, hi = arr.length - k;        // [0, n-k]
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (x - arr[mid] > arr[mid + k] - x)
                lo = mid + 1;                   // 右移
            else
                hi = mid;                       // 左移
        }
        List<Integer> res = new ArrayList<>();
        for (int i = lo; i < lo + k; i++) res.add(arr[i]);
        return res;
    }
}

复杂度

面试官可能追问