Problem

Given somepointsand a pointoriginin two dimensional space, findkpoints out of the some points which are nearest toorigin.
Return these points sorted by distance, if they are same with distance, sorted by x-axis, otherwise sorted by y-axis.

Example

Given points =[[4,6],[4,7],[4,4],[2,5],[1,1]], origin =[0, 0], k =3
return[[1,1],[2,5],[4,4]]

思路

• 自定义comparator, 传入origin

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    /**
     * @param points a list of points
     * @param origin a point
     * @param k an integer
     * @return the k closest points
     */
    public Point[] kClosest(Point[] points, Point origin, int k) {
        MyComparator comp = new MyComparator(origin);
        // if (points == null || points.length == null || points.length <= k) {
        //     Arrays.sort(points, comp);
        //     return points;
        // }

        PriorityQueue<Point> heap = new PriorityQueue<>(points.length, comp);
        for (Point p: points) {
            heap.offer(p);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        Point[] ans = new Point[k];
        for (int i = k - 1; i >= 0; i--) {
            ans[i] = heap.poll();
        }
        return ans;
    }
}


class MyComparator implements Comparator<Point> {
    private Point origin;

    public MyComparator (Point origin) {
        this.origin = origin;
    }

    public int compare (Point p1, Point p2) {
        int dis1 = (p1.x - origin.x) * (p1.x - origin.x) + (p1.y - origin.y) * (p1.y - origin.y);
        int dis2 = (p2.x - origin.x) * (p2.x - origin.x) + (p2.y - origin.y) * (p2.y - origin.y);

        if (dis1 != dis2) {
            return dis2 - dis1;
        }

        if (p1.x != p2.x) {
            return p2.x - p1.x;
        }

        return p2.y - p1.y;
    }
}