LeetCode
Detailed explanation for all 3 methods bellow
Approach 1: Sort1
2
3
4
5
6class Solution{
public int[][] kClosest(int[][] points, int K) {
Arrays.sort(points, (p1, p2) -> p1[0] * p1[0] + p1[1] * p1[1] - p2[0] * p2[0] - p2[1] * p2[1]);
return Arrays.copyOfRange(points, 0, K);
}
}
Min heap, Time Complexity: O(KlogN)1
2
3
4
5
6
7
8
9
10
11class Solution {
public int[][] kClosest(int[][] points, int K) {
PriorityQueue<int[]> q=new PriorityQueue<>((a,b)->(a[0]*a[0]+a[1]*a[1])-(b[0]*b[0]+b[1]*b[1]));
for(int[] point:points) q.offer(point);
int[][] res=new int[K][2];
while(K>0){
res[--K]=q.poll();
}
return res;
}
}
The last solution is based on quick sort, we can also call it Quick Select____ -> Swapping sort (quick sort)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
39class Solution {
public int[][] kClosest(int[][] points, int K) {
int len = points.length, l = 0, r = len - 1;
while (l <= r) {
int mid = patition(points, l, r);
if (mid == K){
break;
}else if (mid < K) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return Arrays.copyOfRange(points, 0, K);
}
private int patition(int[][] A, int l, int r) {
int i = l;
int j = r;
while (i < j) {
while (i < j&&compare(A[j],A[l])>=0) j--;
while (i < j&&compare(A[i],A[l])<=0) i++;
if (i < j) {
int[] tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
}
int[] p = A[l];
A[l]=A[i];
A[i]=p;
return i;
}
private int compare(int[] p1, int[] p2) {
return p1[0] * p1[0] + p1[1] * p1[1] - p2[0] * p2[0] - p2[1] * p2[1];
}
}
