[LintCode] Problem 612 - K Closest Points

Posted on | In ,

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 Point {
    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>() {
        @Override
        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;
}