首页 > itarticle > [leetcode] problem 973 – k closest points to origin

[leetcode] problem 973 – k closest points to origin

admin 11月 13, 2020 0

We have a list of points on the plane. Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

Example

No.1

Input: points = [[1,3],[-2,2]], K = 1

Output: [[-2,2]]

Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

No.2

Input: points = [[3,3],[5,-1],[-2,4]], K = 2

Output: [[3,3],[-2,4]]

(The answer [[-2,4],[3,3]] would also be accepted.)

Note

  1. 1 <= K <= points.length <= 10000
  2. -10000 < points[i][0] < 10000
  3. -10000 < points[i][1] < 10000

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
public int[][] kClosest(int[][] points, int K) {
    int[][] result = new int[K][2];
    PriorityQueue<int[]> minHeap = new PriorityQueue<>(new Comparator<int[]>() {
        
        public int (int[] o1, int[] o2) {
            return (o1[0] * o1[0] + o1[1] * o1[1]) - (o2[0] * o2[0] + o2[1] * o2[1]);
        }
    });

    for (int[] point  : points)
        minHeap.offer(point);

    for (int i = 0; i < K; i++)
        result[i] = minHeap.poll();

    return result;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能