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

题目要求

给定一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。

这里，平面上两点之间的距离是 欧几里德距离（ √(x1 - x2)2 + (y1 - y2)2 ）。

你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案 确保 是 唯一 的。

示例1：

image.png

输入：points = [[1,3],[-2,2]], k = 1
输出：[[-2,2]]
解释：
(1, 3) 和原点之间的距离为 sqrt(10)，
(-2, 2) 和原点之间的距离为 sqrt(8)，
由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。

示例2：

输入：points = [[3,3],[5,-1],[-2,4]], k = 2
输出：[[3,3],[-2,4]]
（答案 [[-2,4],[3,3]] 也会被接受。）

解题思路

求前k个节点，一看就是用小根堆来实现。

在Java中，可以很方便的用PriorityQueue来实现堆，默认就是小根堆。

小根堆的排序规则是节点距离圆心的距离，此处我们没有直接用距离排序，而是用距离的平方排序，因为距离的平方是整数，更方便计算。

为了防止越界，这里我们需要使用long来存储距离的平方值。

Java代码

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        // 使用PriorityQueue小根堆排序
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] p1, int[] p2){
                long dis1 = p1[0] * p1[0] + p1[1] * p1[1];
                long dis2 = p2[0] * p2[0] + p2[1] * p2[1];
                return dis2 - dis1 > 0 ? -1 : 1;
            }
        });
        // 将所有的节点都加入队列
        for(int i = 0; i < points.length; i++){
            queue.offer(points[i]);
        }
        // 取出队列前k个，就是离远点最近的k个点
        int[][] res = new int[k][2];
        for(int i = 0; i < k; i++){
            res[i] = queue.poll();
        }
        return res;
    }
}

总结

今天的题目很简单，是典型的堆的题目。

如果遇到要求最大的K个数、最小的K个数，都可以用堆来解决。

Java中可以用PrioriyQueue来实现堆，默认是小根堆，可以通过自定义Comparator函数来实现大根堆。

        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2){
                return o2 - o1;
            }
        });