Ladder Only
fb面经题，用PriorityQueue,值得注意的地方是Comparator的写法
/**
* 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
*/
private Point origin;
public Point[] kClosest(Point[] points, Point origin, int k) {
// Write your code here
if (points == null || points.length == 0){
return points;
}
this.origin = origin;
Point[] results = new Point[k];
PriorityQueue<Point> pq = new PriorityQueue<Point>(k, sortByDistance);
for (Point point : points){
pq.offer(point);
}
for (int i = 0; i < k; i++){
Point point = pq.poll();
results[i] = point;
}
return results;
}
private Comparator<Point> sortByDistance = new Comparator<Point>(){
public int compare(Point a, Point b){
int diff = 0;
diff = distance(a, origin) - distance(b, origin);
if (diff == 0){
diff = a.x - b.x;
}
if (diff == 0){
diff = a.y - b.y;
}
return diff;
}
};
private int distance(Point a, Point b){
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
}
