K Closest Points to Origin

Posted on | 本文总阅读量 次

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