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

2025-09-22 HGNULB 约 4 分钟

文章信息 11 个分类 6 个标签

分类

LeetCode CodeTop 中等未解决 10-20 字节跳动美团阿里巴巴猿辅导华为虾皮

题目描述

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

题意分析

输入是一个升序数组 arr、一个正整数 k 和一个目标值 x，要求挑出 k 个「离 x 最近」的元素，并且返回结果本身必须升序。这一条经常被忽略：不能挑完之后随手输出，顺序是答案的一部分。

题目对「更接近」给了精确定义：a 比 b 更接近 x，当且仅当 |a - x| < |b - x|；如果两者距离相等，规定较小的那个更接近。也就是说平局要取小，这是一条硬性的决胜规则，而不是可以随意选择的自由度。

约束里最有价值的信号是「arr 已经升序」。距离函数 |a - x| 沿着一条升序数组先单调递减、越过 x 之后再单调递增，是一个「V 字形」。把 V 字形和有序性放在一起看，被选中的 k 个数在下标上不可能跳着分布，否则中间被跳过的数一定比某个被选中的数更近。

边界要留意几处：k 可以等于数组长度，此时整个数组就是答案；x 可以小于所有元素或大于所有元素，答案退化为最左边或最右边的 k 个；数组允许有重复元素，重复值不影响距离比较，但会让「平局取小」变得更频繁。

解法：二分答案窗口左端点

核心思路

由于数组有序，最接近 x 的 k 个元素一定形成连续窗口：若选择了两端却跳过中间元素，中间元素不会比两端同时更远，可替换掉较差端点。

因此只需二分窗口左端点 i，范围为 [0, n-k]。比较相邻窗口 [i, i+k-1] 与 [i+1, i+k]，它们只差 arr[i] 和 arr[i+k]：

若 x - arr[i] > arr[i+k] - x，左端更差，窗口应右移；

否则保留左侧窗口。相等时不右移，正好满足距离相同取较小元素。

判定随 i 单调变化：左端点越右，左侧距离减小、右侧距离增大。二分不变量是最优左端点始终位于 [left, right]，收缩到一点后直接截取长度为 k 的窗口。

解题步骤

初始化 left = 0、right = n - k，表示全部合法窗口起点。

取中点 mid，比较 x - arr[mid] 与 arr[mid + k] - x。

左侧更远则令 left = mid + 1；否则令 right = mid，保留平局时更小的元素。

二分结束后返回 arr[left..left+k)；原数组有序，因此结果无需再排序。

对 [1,2,3,4,5]、k = 4、x = 3，两个候选窗口的外侧元素 1 和 5 距离相同，保留左窗口 [1,2,3,4]。k = n 时起点区间只有 0，直接返回全数组。

代码实现

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0;
        int right = arr.length - k;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 比较两个相邻窗口被替换掉的边界元素。
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        List<Integer> res = new ArrayList<>();
        for (int idx = left; idx < left + k; idx++) {
            res.add(arr[idx]);
        }
        return res;
    }
}

func findClosestElements(arr []int, k int, x int) []int {
    left, right := 0, len(arr)-k
    for left < right {
        mid := left + (right-left)/2
        // 比较两个相邻窗口被替换掉的边界元素。
        if x-arr[mid] > arr[mid+k]-x {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return append([]int(nil), arr[left:left+k]...)
}

复杂度分析

时间复杂度：$O(\log(n-k+1)+k)$，二分起点后复制 k 个结果。

空间复杂度：$O(1)$（不计返回结果）；结果占 $O(k)$。

关键点总结

先证明答案连续，再二分窗口起点；二分的不是目标值本身。

相邻窗口只替换一对外侧元素，比较它们即可判断移动方向。

平局时必须保留左窗口，所以条件只能用 >，不能用 >=。

右边界是 n - k，因为它是窗口起点的上限。

易错点总结

将右边界写成 n - 1，访问 arr[mid + k] 时可能越界。

相等时右移会违反「距离相同取较小值」，对称用例会选错窗口。

二分写成 left <= right 却仍用 right = mid，在单点区间会死循环。

结果循环若使用 <= left + k，会多返回一个元素。

相似题目

题目	难度	考察点
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分定位左右边界
35. 搜索插入位置	简单	二分求下界插入点
704. 二分查找	简单	二分基础模板与区间收缩
1011. 在 D 天内送达包裹的能力	中等	二分答案配可行性判定
378. 有序矩阵中第 K 小的元素	中等	对值域二分并计数
373. 查找和最小的 K 对数字	中等	小根堆取前 K 小