What is the most efficient pattern for solving Find K Closest Elements?

Binary search over the potential window combined with two-pointer selection is the optimal approach, avoiding linear scanning of the entire array.

How should ties be handled when two elements are equally close to x?

Always prefer the smaller element first to maintain ascending order in the final result.

Can this problem be solved with a heap?

Yes, using a min-heap based on distance to x works, but it increases space usage and is less efficient than the binary search approach.

What are common mistakes when implementing two-pointer selection?

Incorrectly expanding pointers beyond array bounds or ignoring tie-break rules leads to wrong results.

Does the array need to be sorted before applying binary search?

Yes, the binary search window approach relies on the array being sorted in ascending order.

#658

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

找到 K 个最接近的元素

给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x （两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。整数 a 比整数 b 更接近 x 需要满足： |a - x| 或者 |a - x| == |b - x| 且 a 示例 1：输入： arr = [1,…

数组双指针二分查找滑动窗口排序

题目描述

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b

示例 1：

输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]

示例 2：

输入：arr = [1,1,2,3,4,5], k = 4, x = -1
输出：[1,1,2,3]

提示：

1 <= k <= arr.length
1 <= arr.length <= 10⁴
arr 按升序排列
-10⁴ <= arr[i], x <= 10⁴

lightbulb

解题思路

方法一：排序

将 $arr$ 中的所有元素按照与 $x$ 的距离从小到大进行排列。取前 $k$ 个元素排序后返回。

时间复杂度 $O(nlogn)$ 。

1

2

3

4

5

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        arr.sort(key=lambda v: abs(v - x))
        return sorted(arr[:k])

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect discussion on edge handling when x is outside arr's range.
question_mark
Ask about tie-breaking rules for elements equidistant to x.
question_mark
Probe understanding of binary search on the answer space versus linear scanning.

warning

常见陷阱

外企场景

error
Forgetting to sort the final k elements before returning.
error
Mismanaging tie-breakers when two numbers are equally close to x.
error
Using linear search which exceeds time limits on large arrays.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Finding k closest elements in an unsorted array requiring O(n log n) sorting.
arrow_right_alt
Returning k farthest elements instead of closest using the same patterns.
arrow_right_alt
Handling streaming data where arr is dynamic and nearest neighbors must update.

help

常见问题

外企场景

继续练习

#786 第 K 个最小的质数分数 #632 最小区间 #611 有效三角形的个数