最接近原点的 K 个点 图解题解

这道题到底在问什么

输入

points=[[1,3], [-2,2], [5,8], [0,1], [3,4], [-1,-1], [2,-3]], k=3

输出

最近的 3 个点

最优解：一步一步想明白

1. 3核心一句话：大小 k 的最大堆，堆顶是当前 k 个里最远的；新点比堆顶近就替换，最后堆里就是最近的 k 个，不用全排序。
2. 4先建空堆：把每个点按距离 d² 加进大小为 3 的最大堆。堆是完全二叉树，画成树看更直观（最远的在堆顶）。
3. 5处理 points[0] = (1,3)。堆里还不够 k=3 个，新点 (1,3)（d²=10）直接放到堆末尾，再按距离上浮到正确位置（远的在上）。
4. 6处理完 (1,3)。堆里还没满 3 个，暂时先把见到的点都留着。
5. 7处理 points[1] = (-2,2)。堆里还不够 k=3 个，新点 (-2,2)（d²=8）直接放到堆末尾，再按距离上浮到正确位置（远的在上）。
6. 8(-2,2) 的距离 d²=8 不大于父节点 (1,3) 的 10，已满足「父 ≥ 子」，上浮结束，位置定下来。
7. 9处理完 (-2,2)。堆里还没满 3 个，暂时先把见到的点都留着。
8. 10处理 points[2] = (5,8)。堆里还不够 k=3 个，新点 (5,8)（d²=89）直接放到堆末尾，再按距离上浮到正确位置（远的在上）。
9. 11新点 (5,8) 的距离 d²=89 比父节点 (1,3) 的 10 还大（最大堆要远的在上面），交换它俩，让它继续往上浮。
10. 12交换完成：更远的 (5,8)（d²=89）升到父位置。继续拿它和再上面的父节点比，直到不再更远。
11. 13处理完 (5,8)。堆里就是目前最近的 3 个点；堆顶 (5,8)（绿色）是这 3 个里最远的，下一个新点只要比它近就能替换它。
12. 14处理 points[3] = (0,1)。堆里已是目前最近的 3 个，堆顶 (5,8)（d²=89）是其中最远的。新点 (0,1) 的 d²=1 比堆顶近，说明它该进前 3 近，挤掉最远的堆顶。
13. 15把堆顶替换成新点 (0,1)（紫色，d²=1）。此刻它可能比孩子近，违反最大堆，需要下沉到正确位置。
14. 16堆顶 (0,1)（d²=1）比孩子 (1,3)（d²=10）近，违反最大堆，得把更远的孩子换上来，让近的继续往下沉。
15. 17交换完成：更远的 (1,3)（d²=10）回到上面。继续拿沉下去的 (0,1) 和它的孩子比，直到就位。
16. 18节点 (0,1)（d²=1）已不小于它的孩子，满足最大堆「父 ≥ 子」，下沉结束，堆顶重新成为当前最远点。
17. 19处理完 (0,1)。堆里就是目前最近的 3 个点；堆顶 (1,3)（绿色）是这 3 个里最远的，下一个新点只要比它近就能替换它。
18. 20处理 points[4] = (3,4)。新点 (3,4) 的 d²=25 不比堆顶 (1,3)（d²=10）近，进不了「最近的 3 个」，堆不变，直接丢弃。
19. 21处理完 (3,4)。堆里就是目前最近的 3 个点；堆顶 (1,3)（绿色）是这 3 个里最远的，下一个新点只要比它近就能替换它。
20. 22处理 points[5] = (-1,-1)。堆里已是目前最近的 3 个，堆顶 (1,3)（d²=10）是其中最远的。新点 (-1,-1) 的 d²=2 比堆顶近，说明它该进前 3 近，挤掉最远的堆顶。
21. 23把堆顶替换成新点 (-1,-1)（紫色，d²=2）。此刻它可能比孩子近，违反最大堆，需要下沉到正确位置。
22. 24堆顶 (-1,-1)（d²=2）比孩子 (-2,2)（d²=8）近，违反最大堆，得把更远的孩子换上来，让近的继续往下沉。
23. 25交换完成：更远的 (-2,2)（d²=8）回到上面。继续拿沉下去的 (-1,-1) 和它的孩子比，直到就位。
24. 26节点 (-1,-1)（d²=2）已不小于它的孩子，满足最大堆「父 ≥ 子」，下沉结束，堆顶重新成为当前最远点。
25. 27处理完 (-1,-1)。堆里就是目前最近的 3 个点；堆顶 (-2,2)（绿色）是这 3 个里最远的，下一个新点只要比它近就能替换它。
26. 28处理 points[6] = (2,-3)。新点 (2,-3) 的 d²=13 不比堆顶 (-2,2)（d²=8）近，进不了「最近的 3 个」，堆不变，直接丢弃。
27. 29处理完 (2,-3)。堆里就是目前最近的 3 个点；堆顶 (-2,2)（绿色）是这 3 个里最远的，下一个新点只要比它近就能替换它。
28. 30走完所有点，堆里留下的就是离原点最近的 3 个点：(0,1)、(-1,-1)、(-2,2)。堆顶 (-2,2)（绿色）是这 3 个里最远的。全程只维护了一个大小 3 的堆，没对全部点排序。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

import heapq
class Solution:
    def kClosest(self, points, k):
        h = []                       # 最大堆：存 (-d², point)
        for x, y in points:
            d = x * x + y * y
            if len(h) < k:
                heapq.heappush(h, (-d, x, y))
            elif -d > h[0][0]:       # d < 堆顶距离 → 更近
                heapq.heapreplace(h, (-d, x, y))
        return [[x, y] for _, x, y in h]

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        priority_queue<pair<int,int>> pq;   // 最大堆: (d², idx)
        for (int i = 0; i < (int)points.size(); ++i) {
            int d = points[i][0]*points[i][0] + points[i][1]*points[i][1];
            if ((int)pq.size() < k) pq.push({d, i});
            else if (d < pq.top().first) { pq.pop(); pq.push({d, i}); }
        }
        vector<vector<int>> res;
        while (!pq.empty()) { res.push_back(points[pq.top().second]); pq.pop(); }
        return res;
    }
};

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        // 最大堆: 按 d² 从大到小, 堆顶是当前最远的点
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (a, b) -> b[0] - a[0]);
        for (int[] p : points) {
            int d = p[0] * p[0] + p[1] * p[1];
            if (pq.size() < k) pq.offer(new int[]{d, p[0], p[1]});
            else if (d < pq.peek()[0]) {   // 比堆顶近才替换
                pq.poll();
                pq.offer(new int[]{d, p[0], p[1]});
            }
        }
        int[][] res = new int[k][2];
        for (int i = 0; i < k; i++) {
            int[] t = pq.poll();
            res[i] = new int[]{t[1], t[2]};
        }
        return res;
    }
}

复杂度

面试官可能追问