LeetCode 973. 最接近原点的 K 个点

2022-02-25 HGNULB 约 12 分钟

文章信息 7 个分类 8 个标签

分类

题目描述

✅ 973. 最接近原点的 K 个点

题意分析

给一组平面上的点 points，每个点是 [x, y]，再给一个整数 k。返回距离原点 $(0,0)$ 最近的 k 个点。距离用欧几里得距离衡量，即 $\sqrt{x^2 + y^2}$。

要什么：一个包含 k 个点的集合。题面明确说明答案可以按任意顺序返回，而且保证答案唯一（除了顺序之外）。这句话价值很大——它说明我们不需要对这 k 个点内部再排序，也不需要考虑距离相同时该选谁的稳定性问题。凡是「返回 Top K 且顺序任意」的题，都可以考虑用堆或快速选择把复杂度压到 $O(n \log k)$ 甚至 $O(n)$。

第一个必须抓住的观察是：比较距离时不需要开方。因为 $\sqrt{\cdot}$ 在非负数上是严格单调递增的，所以
\[\sqrt{x_1^2 + y_1^2} < \sqrt{x_2^2 + y_2^2} \iff x_1^2 + y_1^2 < x_2^2 + y_2^2\]
直接用平方距离 $x^2 + y^2$ 作为排序键，既省掉了每个点一次开方运算，更重要的是避免了浮点数——浮点比较存在精度误差，两个数学上相等的距离可能因舍入而比出大小，在边界数据上产生不确定的结果。用整数比较则是精确的。

约束透露的信号：点的数量在 $10^4$ 量级，坐标绝对值上界是 $10^4$。数量决定了 $O(n \log n)$ 的排序完全够用（$10^4 \times 14 \approx 1.4 \times 10^5$）；坐标上界则提醒我们算一下平方和的范围：$2 \times (10^4)^2 = 2 \times 10^8$，虽然仍在 int 内，但这个数字已经接近上界的十分之一，一旦题目把坐标放大到 $10^5$ 就会溢出。养成用 long 存平方距离的习惯，成本为零而风险归零。

边界：k 保证满足 $1 \le k \le n$，所以不必处理 k 越界或 k 为 0；点可以重合、坐标可以为负（平方后自然变正，无需取绝对值）；原点本身可能在点集中，此时它的平方距离是 0，必然入选。

解法：按距离排序截取

核心思路

这道题的问题结构非常干净：给每个点算一个数值键（平方距离），然后要「键最小的 k 个元素」。这是一个标准的 Top K 问题，它有三条主流路线。

第一条是全排序后截取前 k 个，时间 $O(n \log n)$。第二条是维护一个大小为 k 的大顶堆，遍历时若堆未满就入堆、否则与堆顶比较并择优替换，时间 $O(n \log k)$，在 $k \ll n$ 时更优，且天然适合数据流场景（点一个个到来、内存装不下全部）。第三条是快速选择（QuickSelect），借用快排的划分过程，每次只递归包含第 k 个位置的那一半，平均时间 $O(n)$、最坏 $O(n^2)$。

本文采用第一条。选它的理由是：在本题的数据规模下（$n \le 10^4$），$\log n$ 只有 14 左右，排序的实际耗时与快速选择相差无几；而排序路线的正确性是自明的、边界是最少的——不需要处理堆的初始化、不需要处理快速选择在大量重复距离下的退化，也不需要小心翼翼地维护 [left, right] 的划分边界。当题目没有明确要求 $O(n)$ 时，把清晰度放在首位是合理的工程判断。

具体做法只有两步。第一步，用比较器按平方距离升序排序整个 points 数组。比较器里调用一个返回 long 的辅助函数 distance(p) = (long) p[0] * p[0] + (long) p[1] * p[1]，再用 Long.compare 得到比较结果。第二步，取排序后的前 k 个元素返回。

排序完成后成立的不变量是：对任意 $i < j$，points[i] 到原点的平方距离不大于 points[j] 的。由此可直接断言前 k 个元素就是距离最小的 k 个——若存在某个下标不小于 k 的点比前 k 个中的某一个更近，就与升序矛盾。距离相同的点谁排前面无所谓，因为题面允许任意顺序且保证答案唯一。

有两个实现细节值得点明。其一，比较器必须写成 Long.compare(distance(a), distance(b))，而不能写成 (int)(distance(a) - distance(b))——两个 long 相减的结果强转成 int 时可能截断符号位，把「更小」判成「更大」，导致排序结果错乱甚至抛出 Comparison method violates its general contract 异常。其二，Arrays.copyOf(points, k) 返回的是浅拷贝，新数组里装的还是原来那些 int[] 的引用，这对本题完全够用（我们只是要返回这些点，不会再修改它们），且省下了逐点深拷贝的开销。

解题步骤

定义辅助函数 distance(p)，返回 long 类型的平方距离。为什么不开方：平方根是单调函数，不改变大小关系；跳过开方既省了 $n$ 次浮点运算，又把比较从浮点变回整数，彻底消除精度隐患。为什么先把 p[0]、p[1] 赋给 long 变量再相乘：若写成 (long)(p[0] * p[0])，乘法会先在 int 域内完成再提升，溢出已经发生，强转救不回来；必须让乘法本身在 64 位下进行。

用 Arrays.sort(points, comparator) 按平方距离升序排序。为什么可以原地排序入参：题目没有要求保留原顺序，直接在 points 上排序省去一次数组拷贝。若题目要求不修改入参，则应先克隆。

比较器用 Long.compare(...) 而不是相减。为什么：相减可能溢出（两个接近 $\pm 2^{63}$ 的值相减），强转 int 更会截断；Long.compare 由标准库保证返回正确的三态结果，且语义一目了然。

返回 Arrays.copyOf(points, k)。为什么用 copyOf 而不是直接返回 points：题目要求返回恰好 k 个点，直接返回整个数组会多带出 n - k 个。为什么浅拷贝够用：结果只需要引用这些点，不涉及后续修改。

Go 版用 sort.Slice 配 less 函数，再 copy 前 k 个。为什么 less 必须用严格小于：sort.Slice 要求传入的是严格弱序，用 <= 会让相等元素互相「小于」对方，行为未定义。

以 具体用例 points = [[3,3],[5,-1],[-2,4]], k = 2 走一遍，预期答案是 [[3,3],[-2,4]]（顺序任意）。

计算平方距离：
[3,3] → $3^2 + 3^2 = 9 + 9 = 18$。
[5,-1] → $5^2 + (-1)^2 = 25 + 1 = 26$。注意 $y = -1$ 平方后是正的 1，负坐标不需要任何特殊处理，这也是用平方距离而非坐标本身作键的又一个好处。
[-2,4] → $(-2)^2 + 4^2 = 4 + 16 = 20$。

排序：按 18、20、26 升序排列，得到 points = [[3,3], [-2,4], [5,-1]]。此刻不变量成立——数组自左向右平方距离单调不减。

截取：取前 k = 2 个，返回 [[3,3], [-2,4]]。

手工核对：三个点的真实距离分别是 $\sqrt{18} \approx 4.243$、$\sqrt{26} \approx 5.099$、$\sqrt{20} \approx 4.472$，最近的两个确实是 [3,3] 与 [-2,4]。可以看到，用平方距离排出的顺序与用真实距离排出的顺序完全一致，开方这一步对结果毫无贡献，纯属浪费。

再看一个体现「距离相同」的用例 points = [[1,0],[0,1],[2,0]], k = 2：平方距离分别是 1、1、4。前两个点距离相同，排序后它们的相对顺序取决于排序算法是否稳定，但无论是 [[1,0],[0,1]] 还是 [[0,1],[1,0]] 都是正确答案——题面允许任意顺序。这就是「顺序任意」这条约束帮我们省掉的一整类边界讨论。

代码实现

class Solution {
    // 题目只要求返回任意顺序的前 k 个最近点，不需要保持稳定性或额外次序。
    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;
    }
}

func kClosest(points [][]int, k int) [][]int {
    // 题目只要求返回任意顺序的前 k 个最近点，不需要保持稳定性或额外次序。
    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
}

复杂度分析

时间复杂度：$O(n \log n)$。凭什么：全部代价来自排序，比较次数是 $O(n \log n)$，每次比较调用两次 distance——两次乘法一次加法，都是常数。截取前 k 个是 $O(k)$，被排序吸收。若改用大小为 k 的堆可降到 $O(n \log k)$，改用快速选择可降到平均 $O(n)$；在 $n \le 10^4$ 的本题规模下三者实测差距很小，但在 $k \ll n$ 或 $n$ 上百万时差距会显现。

空间复杂度：Java 为 $O(n)$，Go 为 $O(\log n)$。凭什么：Java 的 Arrays.sort(T[], Comparator) 对对象数组使用 TimSort，需要 $O(n)$ 的归并辅助空间（这与对基本类型数组使用的双轴快排不同，后者只要 $O(\log n)$ 栈空间）；Go 的 sort.Slice 使用 pdqsort，是原地排序，只消耗 $O(\log n)$ 的递归栈。返回的结果数组属于输出，通常不计入额外空间。堆解法的空间是 $O(k)$，快速选择是 $O(1)$ 或 $O(\log n)$，都优于 Java 的排序路线——这是选择排序路线所付出的代价。

关键点总结

单调变换可以整体省略。$\sqrt{\cdot}$、$\log(\cdot)$、乘以正常数这类严格单调递增的变换，作用在排序键上不改变任何比较结果，因此可以直接不做。识别并剥掉这类无用运算，既提速又把浮点变回整数，是数值题的通用第一刀。

能用整数比较就绝不用浮点比较。浮点的舍入误差会让数学上相等的两个值比出大小，在边界数据上产生不可复现的错误；平方距离恰好是整数，天然规避了这个问题。

乘法的类型提升要发生在乘法之前。(long) a * a 是对的，(long) (a * a) 是错的——后者的溢出在强转之前就已经发生。这条规则在所有涉及大数乘法的题目中通用。

比较器一律用 Integer.compare / Long.compare，不要写相减。相减在两端数值跨度大时会溢出，把大小关系反转，Java 还可能因为比较器不自洽而直接抛异常。这是面试中一眼就能看出功底的细节。

读题时抓住「顺序任意」「答案唯一」这类松弛条件，它们往往能砍掉一整类边界讨论（这里砍掉了「距离相同选谁」和「结果内部要不要排序」），也为使用堆和快速选择这类不保序的算法扫清障碍。

在数据规模不吃紧时，优先选边界最少、正确性最自明的方案。排序路线在本题只比快速选择慢一个 $\log$ 因子，却省去了划分边界、重复元素退化等一系列坑；把复杂度优化留到规模真正需要时再做。

面试视角：这题被问到时，只写排序通常会被追问「还有更快的吗」。标准答法是主动摆出三条路线并给出选择依据：排序 $O(n \log n)$，最简单、边界最少；大顶堆 $O(n \log k)$，当 $k \ll n$ 时更优，且是唯一能处理「点以数据流形式到来、无法全部装入内存」这一变体的方案；快速选择平均 $O(n)$，理论最优，但最坏 $O(n^2)$，需要随机化选取基准来规避，且在大量重复距离时要用三路划分。能说清「数据流场景只能用堆」这一条，比背出快速选择的代码更能体现理解深度。另外务必主动提一句「不开方」和「用 long 防溢出」，这两点是面试官检查细节意识的常用抓手。

易错点总结

错误写法：比较器写成 (a, b) -> (int)(distance(a) - distance(b)) → 用例中若存在平方距离分别为 $2 \times 10^8$ 与 1 的两个点尚且安全，但把坐标范围放大后两个 long 相减的结果超出 int 范围，强转截断导致正负号翻转，排序结果错乱；Java 还可能抛出 Comparison method violates its general contract。

错误写法：distance 写成 return (long)(p[0] * p[0] + p[1] * p[1]); → 用例 points = [[50000, 50000]]（若题目放宽坐标范围），p[0] * p[0] 在 int 域内已经溢出成负数，外层强转 long 救不回来，算出的距离是个负值，该点会被误判为最近。类型提升必须作用在乘法的操作数上。

错误写法：用 Math.sqrt 算真实距离并用 double 比较 → 逻辑上多数情况能过，但两个数学上相等的距离（如 $\sqrt{50}$ 与 $\sqrt{50}$ 由不同坐标算出）可能因浮点舍入而比出大小，在「答案唯一」的判定下产生不确定行为；同时白白多了 $n$ 次开方运算。

错误写法：用 Math.abs(p[0]) + Math.abs(p[1])（曼哈顿距离）代替平方距离 → 用例 points = [[2,2],[0,3]], k = 1，曼哈顿距离是 4 与 3，会选出 [0,3]；但平方距离是 8 与 9，正确答案是 [2,2]。题目要的是欧几里得距离，两种度量给出的排序并不一致。

错误写法：直接返回排序后的 points 而不截取 → 用例 points = [[3,3],[5,-1],[-2,4]], k = 2，返回了三个点而不是两个，长度不符直接判错。

错误写法：Arrays.copyOf(points, k) 写成 Arrays.copyOfRange(points, 1, k + 1) → 用例同上，跳过了最近的那个点而多带了一个较远的点，返回 [[-2,4],[5,-1]]，答案错误。截取必须从下标 0 开始。

错误写法：改用大顶堆但把比较方向写反成小顶堆 → 用例 points = [[3,3],[5,-1],[-2,4]], k = 2，小顶堆在超出 k 个时弹出的是最近的点，最终留在堆里的是最远的两个，返回 [[-2,4],[5,-1]]。求最小的 K 个必须用大顶堆，堆顶是当前候选中最差的那个，便于被更好的替换。

错误写法：改用快速选择但递归两边 → 用例是 $10^4$ 个点时复杂度退回 $O(n \log n)$，失去了快速选择的全部优势；正确写法是只递归包含第 k 个位置的那一侧。

错误写法：改用快速选择且固定取首元素作基准 → 用例是点已按距离有序时，每次划分只能减少一个元素，复杂度退化成 $O(n^2)$，$10^4$ 个点约 $10^8$ 次操作，接近超时。必须随机化选基准。

错误写法：Go 中 less 函数写成 distance(points[i]) <= distance(points[j]) → sort.Slice 要求严格弱序，相等元素互判为「小于」会触发未定义行为，某些输入下会 panic 或产生错误顺序。

错误写法：Go 中写 res := points[:k] 直接返回切片 → 返回的切片与 points 共享底层数组，若调用方随后修改 points 会连带影响结果；虽然本题判题不会这么做，但显式 copy 一份是更稳妥的习惯。

相似题目

题目	难度	考察点
215. 数组中的第K个最大元素	中等	只要第 K 个元素本身而非前 K 个集合，是快速选择最纯粹的应用场景
347. 前 K 个高频元素	中等	排序键要先用哈希表统计频次得到，还可用桶排序按频次分桶做到 $O(n)$
692. 前K个高频单词	中等	频次相同时要按字典序，比较器是二级的，且结果必须有序，不能用「顺序任意」偷懒
703. 数据流中的第 K 大元素	简单	数据流场景下排序与快速选择都失效，只能用固定大小 K 的小顶堆增量维护
1046. 最后一块石头的重量	简单	反复取出最大的两个再放回差值，考的是堆的动态增删而非一次性取 Top K
658. 找到 K 个最接近的元素	中等	数组已有序，可用二分定位长度为 K 的最优窗口起点，做到 $O(\log n + k)$
786. 第 K 个最小的质数分数	中等	候选规模是 $O(n^2)$ 无法物化，只能用堆做多路归并或在值域上二分
剑指 Offer 40. 最小的k个数	简单	与本题同构的一维版本，排序键就是元素本身，可直接对照练三种解法
面试题 17.14. 最小K个数	中等	数据规模更大，是检验快速选择相对排序优势的合适场景
LCR 076. 数组中的第 K 个最大元素	中等	与 215 同题，可直接套用