LeetCode 658. 找到 K 个最接近的元素
题目描述
题意分析
从已经升序排列的数组中选出最接近
x的k个元素，并按升序返回。比较时先看与x的绝对距离，距离相同则优先选择数值较小的元素。重复值仍按各次出现分别计数，不能先去重。
x不一定在数组中，也可能位于整个数组的范围之外；k保证在1到数组长度之间。
解法：二分答案窗口左端点
核心思路
[!blue]
在有序数组中，离
x的距离会先减小再增大。如果已经选中了两端的元素，中间被跳过的元素不会比两个端点中较远的那个更差。因此可以不断补上中间空缺，得到一个同样最优的连续窗口；重复值可能对应不同下标选择，但不影响存在这样的窗口。于是问题变为确定长度为
k的窗口从哪里开始，合法起点为[0, n - k]。起点mid和mid + 1的两个窗口只差一对元素：前者包含arr[mid]，后者用arr[mid + k]替换它，中间的k - 1个元素完全相同。比较
x - arr[mid]与arr[mid + k] - x。当x位于这两个边界值之间时，它们正好是左右距离；左式更大应向右找，否则保留左侧，距离相等时也保留较小的左值。若两个边界都在x左侧，比较会引导窗口右移；若都在右侧，则引导窗口左移。这个比较等价于判断
arr[mid] + arr[mid + k] < 2 * x。随着起点右移，两项都不会减小，所以条件只能从成立变为不成立，能够二分寻找分界：成立时令left = mid + 1，否则令right = mid。代码使用差值形式，二分时不需要真的求这个和。这里必须保留有符号差，不能直接替换为两个绝对距离。两个相同的边界值可能同在
x一侧，此时两个相邻窗口的值虽相同，仍要沿着靠近x的方向继续寻找；绝对距离的平局会丢失这个方向信息。左右起点相遇时，截取从该位置开始的
k个元素即可。原数组已经有序，结果无需再排序；k == n时起点范围只有零，循环自然跳过。
解题步骤
- 将窗口起点范围初始化为
left = 0、right = n - k。- 在
left < right时取中点mid，比较窗口两侧的有符号差。- 若
x - arr[mid] > arr[mid + k] - x，令left = mid + 1；否则令right = mid。- 二分结束后复制区间
[left, left + k)，按原有升序返回。
代码实现
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]...)
}
复杂度分析
设数组长度为 $n$。
- 时间复杂度：$O(\log(n-k+1)+k)$，先二分合法起点，再复制 $k$ 个结果。
- 辅助空间复杂度：$O(1)$，只维护二分边界；返回结果另占 $O(k)$。
关键点总结
[!green]
- 最优值集合可以由一个连续窗口表示，二分对象是窗口起点。
- 相邻窗口只替换两个边界元素，有符号比较构成单调判据。
- 平局保留左侧，符合距离相同优先较小值的规则。
易错点总结
[!yellow]
- 右边界是
n - k，不是n - 1；循环中mid < right，因此arr[mid + k]才不会越界。- 把比较改成绝对距离会在重复边界值位于目标同侧时失去正确方向，不能机械替换。
- 相等时不能右移，必须保留可能更优的左窗口。
- 本写法使用
left < right和right = mid，不要改成闭区间搜索的终止条件而不调整更新规则。- 返回区间右端不包含
left + k，否则会多返回一个元素。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 35. 搜索插入位置 | 简单 | 先通过下界定位目标附近，再利用有序性确定最近的连续k项窗口。 |