Given some points and an origin point in two-dimensional space, find k points which are nearest to the origin.
Return these points sorted by distance, if they are same in distance, sorted by the x-axis, and if they are same in the x-axis, sorted by y-axis.
Example
No.1
Input: points = [[4,6],[4,7],[4,4],[2,5],[1,1]], origin = [0, 0], k = 3
Output: [[1,1],[2,5],[4,4]]
No.2
Input: points = [[0,0],[0,9]], origin = [3, 1], k = 1
Output: [[0,0]]
Code
1
2
3
4
5
6
|
public class {
int x;
int y;
Point() { x = 0; y = 0; }
Point(int a, int b) { x = a; y = b; }
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
public Point[] kClosest(Point[] points, Point origin, int k) {
Point[] result = new Point[k];
PriorityQueue<Point> minHeap = new PriorityQueue<>(new Comparator<Point>() {
public int compare(Point o1, Point o2) {
int distance1 = (o1.x - origin.x) * (o1.x - origin.x)
+ (o1.y - origin.y) * (o1.y - origin.y);
int distance2 = (o2.x - origin.x) * (o2.x - origin.x)
+ (o2.y - origin.y) * (o2.y - origin.y);
if (distance1 == distance2)
return o1.x == o2.x ? (o1.y - o2.y) : o1.x - o2.x;
return distance1 - distance2;
}
});
for (Point point : points)
minHeap.offer(point);
for (int i = 0; i < k; i++)
result[i] = minHeap.poll();
return result;
}
|
近期评论