What is the best approach for K Closest Points to Origin?

Using a max-heap for dynamic tracking of k closest points or Quickselect for partial sorting usually provides optimal performance.

Should I compute sqrt for Euclidean distance?

No, comparing squared distances is sufficient and avoids extra computation, maintaining correct order for selection.

Can the answer be in any order?

Yes, the points can be returned in any order as long as the closest k points are selected.

What is the time complexity for this problem?

Max-heap approach runs in O(n log k), Quickselect averages O(n), and full sort requires O(n log n).

How do I handle multiple points at the same distance?

Any subset of points at the same distance can be chosen as long as k points are returned; order does not matter.

#973

Medium

auto_awesome数组·数学

LeetCode 题解工作台

最接近原点的 K 个点

给定一个数组 points ，其中 points[i] = [x i , y i ] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。这里，平面上两点之间的距离是欧几里德距离（ √(x 1 - x 2 ) 2 + (y 1 - y 2 ) 2 ）。…

数组数学分治几何排序

题目描述

给定一个数组 points ，其中 points[i] = [x_i, y_i] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。

这里，平面上两点之间的距离是 欧几里德距离（ √(x₁ - x₂)² + (y₁ - y₂)² ）。

你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案确保是唯一的。

示例 1：

输入：points = [[1,3],[-2,2]], k = 1
输出：[[-2,2]]
解释： 
(1, 3) 和原点之间的距离为 sqrt(10)，
(-2, 2) 和原点之间的距离为 sqrt(8)，
由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。

示例 2：

输入：points = [[3,3],[5,-1],[-2,4]], k = 2
输出：[[3,3],[-2,4]]
（答案 [[-2,4],[3,3]] 也会被接受。）

提示：

1 <= k <= points.length <= 10⁴
-10⁴ < x_i, y_i < 10⁴

lightbulb

解题思路

方法一：自定义排序

我们将所有点按照与原点的距离从小到大排序，然后取前 $k$ 个点即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组 $\textit{points}$ 的长度。

1

2

3

4

5

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        points.sort(key=lambda p: hypot(p[0], p[1]))
        return points[:k]

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate correctly compute Euclidean distances without using square roots unnecessarily?
question_mark
Do they choose an optimal approach between heap, Quickselect, and full sort for k closest points?
question_mark
Can they handle edge cases such as multiple points at the same distance or k equal to array length?

warning

常见陷阱

外企场景

error
Using sqrt unnecessarily, increasing computation time instead of comparing squared distances.
error
Not maintaining max-heap of size k, causing extra space usage or wrong points selection.
error
Failing to handle cases where multiple points have identical distances to the origin.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find k farthest points from origin using a min-heap or modified Quickselect.
arrow_right_alt
Find k closest points to an arbitrary point (x0, y0) instead of the origin.
arrow_right_alt
Find k closest points in 3D space using Euclidean distance in three dimensions.

help

常见问题

外企场景

继续练习

#347 前 K 个高频元素 #215 数组中的第K个最大元素 #1738 找出第 K 大的异或坐标值