612.K Closest Points

1.Description(Medium)

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]]

Tags

Heap LinkedIn Amazon

2.Code

维护一个大小为k的递减栈，每次有比栈顶小的元素就把栈顶poll出，让新的值入栈，最后倒序输入一个数组即可。

public class Solution_612 {
    /**
     * @param points a list of points
     * @param origin a point
     * @param k an integer
     * @return the k closest points
     */
    //这里不用一个全局变量的话，参数里就要改成final Point origin了
    private Point original=null;
    public Point[] kClosest(Point[] points, Point origin, int k) {
        original=origin;
        //这是一个递减栈，栈顶是当前最大的距离
        //这里在comparator里面就把distance一样的话按照先x轴再y轴的顺序排好。
        Queue<Point> queue=new PriorityQueue<Point>(k,new Comparator<Point>(){
            @Override
            public int compare(Point a,Point b){
                int distance=getdistance(b,original)-getdistance(a,original);
                if(distance==0)
                    return b.x-a.x;
                if(distance==0)
                    return b.y-a.y;
                return distance;               
            }
        });

        for(int i=0;i<points.length;i++){
            if(i<k){
                queue.offer(points[i]);
            }else{
                Point temp=queue.peek();
                if(getdistance(temp,original)>getdistance(points[i],original)){
                    queue.poll();
                    queue.offer(points[i]);
                }
            }
        }
        //虽然一开始定下了queue的size，但是实际还是要再算一遍
        int size=queue.size();
        Point[] result=new Point[size];
        while(!queue.isEmpty()){
            result[--size]=queue.poll();         
        }
        return result;
    }

    public int getdistance(Point a,Point b){
        int dis=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
        return dis;
    }
}