-
Notifications
You must be signed in to change notification settings - Fork 1
/
KClosestPointsToOrigin.java
68 lines (60 loc) · 1.96 KB
/
KClosestPointsToOrigin.java
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package com.leetcode;
import java.util.PriorityQueue;
public class KClosestPointsToOrigin {
//https://leetcode.com/problems/k-closest-points-to-origin/
class Solution {
public int[][] kClosest(int[][] points, int K) {
int n = points.length;
if(n<=K) return points;
PriorityQueue<Node> maxHeap = new PriorityQueue<>((a, b)->(b.distance() - a.distance()));
for(int[] p : points){
maxHeap.offer(new Node(p[0],p[1]));
if(maxHeap.size() > K)
maxHeap.poll();
}
int[][] result = new int[K][2];
int i = K-1;//just for sorting , optional
while(maxHeap.size() >0){
Node node = maxHeap.poll();
result[i][0] = node.x;
result[i][1] = node.y;
i--;
}
return result;
}
class Node{
int x;
int y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
public int distance(){
return x*x + y*y;
}
}
}
class SolutionAlternative {
public int[][] kClosest(int[][] points, int K) {
if(K>points.length){
return null;
}
PriorityQueue<int[]> maxHeap = new PriorityQueue<int[]>( (p1,p2) -> ((p2[0]*p2[0] + p2[1]*p2[1]) - (p1[0] * p1[0] + p1[1]*p1[1])) );
for(int [] p : points){
maxHeap.offer(p);
if(maxHeap.size() > K){
maxHeap.poll();
}
}
int[][] result = new int[K][2];
int counter = 0;
while(maxHeap.size() > 0){
int[] p = (int[])maxHeap.poll();
result[counter][0] = p[0];
result[counter][1] = p[1];
counter++;
}
return result;
}
}
}