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

升序数组里挑离 x 最近的 k 个数，返回哪一段

给升序（从小到大排好）数组 arr、整数 k 和目标 x，挑出离 x 最近的 k 个数按升序返回；一样近取更小的。题面 arr=[1,2,3,4,5]、k 取 4、x 取 3，答案 [1,2,3,4]：只有 5 离 3 最远，丢掉它。

按距离排个序取前 k 个，慢在哪

给每个数标上到 x 的距离、按距离排序取最小的 k 个再排回升序，也能出答案，但排序要 O(n log n)（大 O 记号，衡量规模对操作量的放大倍数），几十万个数只为挑 k 个全排一遍不值。还有从两头往里夹的双指针：每次把更远的一端往里收一格，缩 n−k 次是 O(n−k)，n 大同样拖。

最优那段的左端点，能二分着定位

答案一定是连续的一段（长度 k，即窗口）。数组有序，离 x 最近的 k 个数必然挨成一排，跳着选总能用更近的相邻数换掉一个更远的，只会更优。所以要定的只有一个量：窗口从哪个下标起。窗口不能越界，左端点最大只到 n−k，被锁在 [0, n−k] 里。

窗口从左往右滑，先越滑越贴近 x、再越滑越远，最优点两侧一边偏小一边偏大，呈单调走向。单调就能用二分每轮砍掉一半候选左端点，不必逐个试。

中点这一格，凭什么就能判定往哪半收

在 [lo, hi] 取中点 mid，比的不是 arr[mid] 和 x，而是窗口边界两个数：arr[mid] 是窗口最左（一右移就被丢），arr[mid+k] 是紧挨右边、还没进来的那个——窗口右挪一格时正是这俩一出一进，谁离 x 更远谁被排除。

若 x−arr[mid] > arr[mid+k]−x，该丢的 arr[mid] 比该纳的更远，左端点偏小，lo 跳到 mid+1、窗口右移；否则（含两边一样远）hi 收到 mid。这支写 hi=mid 不是 hi=mid−1，因为 mid 本身可能就是最优左端点。

拿题面 [1,2,3,4,5] 手算一遍

n 为 5、k 为 4，左端点范围 [lo, hi]=[0, 1]。lo 小于 hi，进循环。mid=(0+1)//2=0，看下标 0 起的窗口 {1,2,3,4}：要丢的 arr[0]=1 离 x 差 3−1=2，要纳的 arr[4]=5 离 x 差 5−3=2。判 2 大于 2 不成立，走 else，hi 收到 0。

此时 lo、hi 都是 0，不再满足 lo 小于 hi，循环停，返回 arr[0:4]={1,2,3,4}，即题面答案。这轮撞上平局：两侧都差 2，走 else 留在左边、丢掉更大的 5。

hi 起手写成 n−1，窗口一伸就出界

二分把左端点范围每轮砍半、约 log(n−k) 轮定位，再切出 k 个数，合起来 O(log(n−k)+k)、空间 O(1)，比排序的 O(n log n) 省一截。

hi 的起点最常写坏：写成 n−1，mid 落到靠后下标时 arr[mid+k] 越过数组末尾读到越界，hi 得从 n−k 起。方向也别抄反：丢左端配 lo=mid+1（写成 lo=mid，比过的 mid 没跨过去会卡着缩不动），丢右端配 hi=mid；判定用 > 而非 ≥，否则平局会偏向更大的数。

Python

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]

C++

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);
    }
};

Java

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;
    }
}