LeetCode 973. 最接近原点的 K 个点
题目描述
题意分析
从给定的二维坐标中，返回到原点欧氏距离最近的
k个点。题目保证答案集合唯一，返回这些点的顺序不限。点
(x, y)到原点的距离为sqrt(x*x + y*y)。只需要比较远近，不需要计算距离本身，因此可以直接比较距离平方。
解法：按距离排序截取
核心思路
[!blue]
平方根函数在非负数上单调递增，所以
x*x + y*y越小，到原点的距离也越小。用距离平方作为排序键，就能保持正确的远近顺序，并避免开平方和浮点数比较。按距离平方将所有点升序排列后，前
k个点的距离都不大于其余点，因此它们就是所需的最近点。距离相同的点之间无需再比较横纵坐标，因为答案不要求特定返回顺序。比较器只负责计算和比较距离平方，排序时移动的是整个坐标数组，保证横纵坐标始终成对。代码将坐标提升为 64 位整数后做乘法，Java 使用
Long.compare比较，Go 直接比较两个距离值。排序会改变输入点数组的排列。返回时只复制前
k个坐标数组的引用到新的外层数组，坐标数据本身没有深拷贝。
解题步骤
- 定义距离平方函数，返回当前点的
x*x + y*y。- 用这个值作为升序排序键，对整个
points数组排序。- 取下标区间
[0, k)中的点，复制到新的结果数组。- 返回结果。
k表示需要的点数，因此最后一个被选中的下标是k-1。
代码实现
class Solution {
public int[][] kClosest(int[][] points, int k) {
// 按距离平方排序，前面恰是所需的最近点。
Arrays.sort(points, (a, b) -> Long.compare(distance(a), distance(b)));
return Arrays.copyOf(points, k);
}
private long distance(int[] p) {
long x = p[0];
long y = p[1];
return x * x + y * y;
}
}
import "sort"
func kClosest(points [][]int, k int) [][]int {
// 按距离平方排序，前面恰是所需的最近点。
sort.Slice(points, func(i, j int) bool {
return distance(points[i]) < distance(points[j])
})
res := make([][]int, k)
copy(res, points[:k])
return res
}
func distance(p []int) int64 {
x := int64(p[0])
y := int64(p[1])
return x*x + y*y
}
复杂度分析
设点的数量为
n。
- 时间复杂度：$O(n\log(n+1)+k)$，排序为 $O(n\log n)$，复制结果中的
k个点引用为 $O(k)$。- 空间复杂度：结果占 $O(k)$；此外，Java 对象数组排序需要 $O(n)$ 辅助空间，Go 排序栈需要 $O(\log(n+1))$ 辅助空间。
关键点总结
[!green]
- 比较平方距离与比较欧氏距离的顺序一致，无需开平方。
- 排序后前
k个点就是答案，不需要额外的位置筛选。- 排序重排输入，结果只复制外层引用，仍共享各点的坐标数组。
易错点总结
[!yellow]
- 使用横纵坐标绝对值之和：这是另一种距离，会改变题目要求的欧氏距离顺序。
- 按距离降序取前
k个：会得到最远的点，排序方向应为升序。- 把
k当成最后一个包含的下标：会多返回一个点，应截取[0, k)。- 分别排序横坐标和纵坐标：会破坏原有点的位置，必须把一对坐标作为整体移动。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 215. 数组中的第K个最大元素 | 中等 | 把排序键换成到原点的距离平方后，可复用堆或快速选择得到前k项。 |
| 703. 数据流中的第 K 大元素 | 简单 | 用大小受限的堆保留排名靠前的候选；本题以到原点的平方距离为排序依据，该题支持持续插入时维护第 k 大。 |
| 347. 前 K 个高频元素 | 中等 | 用大小受限的堆保留排名靠前的候选；本题以到原点的平方距离为排序依据，该题以元素频次为排序依据。 |
| 692. 前K个高频单词 | 中等 | 用大小受限的堆保留排名靠前的候选；本题以到原点的平方距离为排序依据，该题以单词频次和字典序联合排序。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！