K Closest Points to Origin

K Closest Points to Origin

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.)

在二维坐标列表中,寻找出 K 个离原点最近的坐标值

Solution1

List && Map

1
2
3
private int multi(int[] point) {
return point[0] * point[0] + point[1] * point[1];
}
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
class Solution {
public int[][] kClosest(int[][] points, int K) {
if (points.length < K) {
return null;
}

Map<Long, List<Point>> map = new HashMap<>();
List<Long> sort = new ArrayList<>();
for (int[] point : points) {
long val = point[0] * point[0] + point[1] * point[1];
if (map.containsKey(val)){
map.get(val).add(new Point(point));
} else {
List<Point> pointList = new ArrayList<>();
pointList.add(new Point(point));
map.put(val, pointList);
sort.add(val);
}
}

Collections.sort(sort);

int[][] answer = new int[K][2];
int count = 0, i = 0;
while (count < K) {
long val = sort.get(i++);
for (Point point : map.get(val)) {
answer[count++] = new int[]{point.getX(), point.getY()};
}
}
return answer;
}

private class Point {
private int x;
private int y;

private Point(int[] point) {
this.x = point[0];
this.y = point[1];
}

public int getX() {
return this.x;
}

public int getY() {
return this.y;
}
}
}

Solution2

min heap

O (n * logn)

1
2
3
4
5
6
7
8
9
// mock min heap -> poll -> get min element
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
// pq = new PriorityQueue<>((o1, o2) -> o1 - o2);
pq.offer(6);
pq.offer(-3);
pq.offer(9);
pq.offer(0);
pq.offer(9);
// -3 0 6 9 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private int[][] kClosest2(int[][] points, int K) {
PriorityQueue<int[]> pq = new PriorityQueue<>(K, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return multi(a) - multi(b);
}
});

for (int[] point : points) {
pq.offer(point);
}

int[][] result = new int[K][2];
for (int i = 0; i < K; i++) {
result[i] = pq.poll();
}
return result;
}

Solution3

max heap

O (n * logK)

1
2
3
4
5
6
7
8
9
// mock max heap -> poll -> get max element
pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
// pq = new PriorityQueue<>(Collections.reverseOrder());
pq.offer(6);
pq.offer(-3);
pq.offer(9);
pq.offer(0);
pq.offer(9);
// 9 9 6 0 -3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private int[][] kClosest3(int[][] points, int K) {
PriorityQueue<int []> pq = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] a,int[] b){
return -(multi(a) - multi(b));
}
});

for (int[] point : points) {
if (pq.size() < K) {
pq.add(point);
} else if (multi(pq.peek()) > multi(point)) {
pq.poll();
pq.add(point);
}
}

int[][] result = new int[K][2];
for (int i = 0; i < result.length; i++) {
result[i] = pq.poll();
}
return result;
}

Solution4

Quick Select