如何用堆求离原点最近的 K 个点？

简化版

求离原点最近的 K 个点，可以维护大小为 K 的大顶堆，比较键是距离平方 x*x + y*y。堆顶是当前 K 个候选里最远的点，新点更近时替换堆顶。

详细版

这题本质是 Top K，只是比较键从元素值变成“点到原点的距离”。由于平方根不影响大小关系，比较时用距离平方即可，避免浮点计算。

做法：

对每个点计算 dist2 = x*x + y*y。
维护大小为 K 的大顶堆，堆顶是候选中距离最大的点。
堆未满时直接加入。
堆满后，如果新点距离小于堆顶距离，就弹出堆顶并加入新点。
最终堆内就是最近的 K 个点。

int[][] kClosest(int[][] points, int k) {
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) ->
        Integer.compare(dist2(b), dist2(a)) // 大顶堆
    );
    for (int[] p : points) {
        pq.offer(p);
        if (pq.size() > k) pq.poll();
    }
    return pq.toArray(new int[pq.size()][]);
}

int dist2(int[] p) {
    return p[0] * p[0] + p[1] * p[1];
}

时间 O(n log K)，空间 O(K)。如果所有点都在内存里，快速选择平均 O(n) 也是常见对比方案。

完整版教学

一、距离平方为什么够用

点 (x, y) 到原点的欧氏距离是 sqrt(x^2 + y^2)。因为平方根函数在非负数上单调递增，所以比较两个点谁更近时，只比较 x^2 + y^2 就够了，不需要真的开方。

P1=(1,3): dist2 = 1^2 + 3^2 = 10
P2=(-2,2): dist2 = 4 + 4 = 8
因为 8 < 10，所以 P2 更近

这样可以避免浮点误差和额外计算。面试里说出“用距离平方比较”通常是一个加分点，因为它说明你知道比较关系和具体数值之间的区别。

二、为什么最近 K 个要用大顶堆

求最近 K 个点时，我们维护的是“当前最小的 K 个距离”。候选集合里最该被淘汰的是距离最大的那个，所以应该让堆顶保存“最远候选者”。这正好需要大顶堆。

需求	候选集合	合适堆	堆顶含义
最近 K 个点	距离最小的 K 个	大顶堆	候选中最远，淘汰门槛
最远 K 个点	距离最大的 K 个	小顶堆	候选中最近，淘汰门槛
第 K 大数值	最大的 K 个数	小顶堆	第 K 大

这个规律可以统一记忆：堆顶要放“最容易被淘汰”的候选者。最近 K 个里最容易淘汰的是最远点，所以用大顶堆。

三、用例子看堆如何筛选

设点集为 [(1,3), (-2,2), (5,8), (0,1)]，K=2。距离平方分别是 10, 8, 89, 1。维护大小为 2 的大顶堆。

放 (1,3)[10]       heap: 10
放 (-2,2)[8]       heap: 10,8       候选是 10 和 8
放 (5,8)[89]       size=3，弹 89    候选仍是 10 和 8
放 (0,1)[1]        size=3，弹 10    候选变成 8 和 1

最终最近 2 个点：(-2,2), (0,1)

如果用小顶堆保存最近候选，堆顶会是当前最近点，反而无法快速淘汰最远候选。理解“堆顶是淘汰门槛”比死记大小顶堆更可靠。

四、比较器和整数溢出的坑

如果坐标范围较大，x*x + y*y 可能超过 int。例如 x=100000 时，x*x=10^10，已经超过 32 位整数。实际写代码时可以用 long 计算距离平方。

long dist2(int[] p) {
    return 1L * p[0] * p[0] + 1L * p[1] * p[1];
}

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) ->
    Long.compare(dist2(b), dist2(a))
);

比较器也不要写成 (int)(dist2(b) - dist2(a))，因为差值可能溢出或截断。用 Long.compare 更稳。面试官经常借这个细节检查你是否只会背模板。

五、和排序、快速选择怎么选

最直接的方法是把所有点按距离排序，再取前 K 个，复杂度 O(n log n)。堆法是 O(n log K)，当 K 远小于 n 时更省。快速选择平均 O(n)，但会修改数组，最坏可能退化，且实现细节更多。

排序：      全部排好，简单但多做了完整顺序
堆：        只维护 K 个候选，适合 K 小或数据流
快速选择：  平均更快，适合离线数组，需处理 pivot 退化

如果题目要求“结果可以任意顺序”，堆法输出不需要再排序。如果要求按距离升序输出，就要对堆中结果再排序一次，代价 O(K log K)。

六、常见误区与追问

记忆钩子：最近 K 个用大顶堆，因为堆顶站着“当前最远的候选淘汰者”。

误区：必须计算真正的欧氏距离。 开方不改变大小关系，用距离平方即可。
误区：最近 K 个应该用小顶堆。 小顶堆会把最近点放堆顶，但我们需要快速淘汰最远候选。
误区：返回的堆数组天然按距离有序。 堆内数组不是排序结果，有顺序要求要额外排序。
追问：坐标很大会怎样？ 距离平方可能整数溢出，应使用 long。
追问：K 等于点数怎么办？ 可以直接返回全部点，堆法也正确但多做了工作。
追问：为什么快速选择可能更快？ 它平均 O(n) 找到距离第 K 小的边界，但不适合流式数据。

七、加强记忆

K 个最近点就是 Top K 的几何版本：比较键不是数值本身，而是距离平方。维护“最近的 K 个”时，候选中最该被淘汰的是最远点，所以使用大小为 K 的大顶堆。新点更近就替换堆顶，不更近就丢弃。记忆时把三个点串起来：距离平方避免开方，大顶堆维护淘汰门槛，O(n log K) 适合 K 小或流式输入。

简化版

详细版