K Closest Points

Given some points and a point origin in two dimensional space, find k points out of the some points which are nearest to origin. Return these points sorted by distance, if they are same with distance, sorted by x-axis, otherwise sorted by y-axis.Have you met this question in a real interview? YesProblem Correction

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

nlogn k

快排

class Solution {
    private Point origin;
    public Point[] kClosest(Point[] points,Point origin,int k){
        this.origin = origin;
        quickSelect(points,0, points.length-1, k-1);

        Point[] ans = new Point[k];
        for(int i = 0; i < k; i++){
            ans[i] = points[i];
        }

        

        return ans;

    }

    public void quickSelect(Point[] points, int start, int end, int kth){
        int pivot = start + (start + end) /2;

        long pivot_dis = getDistance();

        int low = start, hi = end;

        while(low <= hi){
            while(low <= hi && compare(Point[pivot], Point[low],pivot_dis) < 0){
                low++;
            }

            while(low <= hi && compare(Point[pivot], Point[hi],pivot_dis) > 0){
                hi++;
            }

            if(low <= hi){
                Point tmp = Point[low];
                Point[low] = Point[hi];
                Point[hi] = tmp;
                low++;
                hi--;
            }
        }

        if(low <= kth){
            quickSelect(points,low, end,kth);
        }

        if(hi >= kth){
            quickSelect(points, start, hi,kth);
        }
    }

    public int compare(Point pivot, Point p, long pivot_dis){
        long dis = getDistance(p, origin);

        if(dis != pivot_dis){
            return dis < pivot_dis ? -1 : 1;
        }

        else{
            return pivot.x == p.x ? p.y - pivot.y : p.x - pivot.x;
        }
    }

    public long geDistance(Point p1, Point p2){

            return (p1.x - p2.x) *(p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    }
}