LeetCode 973中等排序 · Top K
最接近原点的 K 个点 图解题解
这道题到底在问什么
给一组平面点 points，返回距离原点最近的 k 个点。
- points
- [[1,3],[-2,2],[5,8],[0,1],[2,-2]]
- k
- 2
- 输出
- [[0,1],[-2,2]]（距离 1、8 最小）
最优解：一步一步想明白
⚠️ 容易写错的地方
✗ 错：用 x+y 比距离
✓ 对：用 x*x+y*y
距离来自平方和，且坐标可能为负
✗ 错：对距离开根号
✓ 对：直接比较平方距离
开根号不改变大小顺序，只会多算
完整代码（Python / C++ / Java）
Python
class Solution:
def kClosest(self, points, k):
# 按到原点的平方距离排序，取前 k 个
points.sort(key=lambda p: p[0]*p[0] + p[1]*p[1])
return points[:k]C++
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
sort(points.begin(), points.end(), [](auto& a, auto& b) {
return a[0]*a[0]+a[1]*a[1] < b[0]*b[0]+b[1]*b[1]; // 比平方距离
});
return vector<vector<int>>(points.begin(), points.begin() + k);
}
};Java
class Solution {
public int[][] kClosest(int[][] points, int k) {
Arrays.sort(points, (a, b) ->
(a[0]*a[0]+a[1]*a[1]) - (b[0]*b[0]+b[1]*b[1])); // 比平方距离
return Arrays.copyOfRange(points, 0, k);
}
}套路模板 · 按 key 取前 K
class Solution:
def topK(self, items, k):
items.sort(key=lambda x: key(x))
return items[:k]复杂度
时间复杂度
O(n log n)
对所有点按平方距离排序
空间复杂度
O(1)
原地排序(不计输出)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最接近原点的 K 个点 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心思路是什么？+
按到原点的平方距离 x²+y² 排序，取前 k 个；不用开根号(单调一致)。
有更快的解法吗？+
① 大小为 k 的最大堆 O(n log k)；② 快速选择 partition 找第 k 近 O(n) 平均。n≫k 时堆/快选比全排序 O(n log n) 快。
为什么用平方距离不开根号？+
距离=√(x²+y²)，开根是单调函数不改变大小顺序；直接比 x²+y² 省掉 sqrt、还避免浮点误差。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。