LIKE CODING: LeetCode [973] K Closest Points to Origin

973. K Closest Points to Origin

Medium

We have a list of points on the plane. Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)

Note:

1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000

Nlog(K)

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        priority_queue<pair<int, vector<int>>> pq;
        for(auto p: points)
        {
            int ds = p[0]*p[0] + p[1]*p[1];
            pq.push(make_pair(-ds, p));
        }
        
        vector<vector<int>> ret;
        for(int i=0; i<K; ++i)
        {
            ret.push_back(pq.top().second);
            pq.pop();
        }
        
        return ret;
    }
};

class Solution {
    double getD(vector<int>& p){
        return p[0]*p[0] + p[1]*p[1];
    }
    int partition(vector<vector<int>>& points, int l, int h){
        double pivot = getD(points[h]);
        int i = l-1;
        for(int j=l; j<h; ++j){
            if(getD(points[j])<=pivot){
                swap(points[++i], points[j]);
            }
        }
        swap(points[++i], points[h]);
        return i;
    }
    
    void quicksort(vector<vector<int>>& points, int l, int h, int K, vector<vector<int>>& ret){
        if(l>h) return;
        int p = partition(points, l, h);
        if(p<=K-1){
            ret.insert(ret.begin(), points.begin()+l, points.begin()+p+1);
            quicksort(points, p+1, h, K, ret);
        }else{
            quicksort(points, l, p-1, K, ret);
        }
    }
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        vector<vector<int>> ret;
        quicksort(points, 0, points.size()-1, K, ret);
        return ret;
    }
};

//Java, maxHeap, nlog(k)
class Solution {
    public int[][] kClosest(int[][] points, int K) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a,b) -> Integer.compare(b[0]*b[0]+b[1]*b[1], a[0]*a[0]+a[1]*a[1]));
        for(int[] p : points){
            maxHeap.add(p);
            if(maxHeap.size()>K) maxHeap.poll();
        }
        
        int[][] ret = new int[maxHeap.size()][2];
        int i = 0;
        while(!maxHeap.isEmpty()){
            ret[i++] = maxHeap.poll();
        }
        
        return ret;
    }
}

//Quick Sort, O(n)
class Solution {
    void swap(int[][] points, int i, int j){
        int[] tmp = points[i];
        points[i] = points[j];
        points[j] = tmp;
    }
    boolean isCloserOrEqual(int[] p1, int[] p2){
        return p1[0]*p1[0]+p1[1]*p1[1] <= p2[0]*p2[0]+p2[1]*p2[1];
    }
    int partition(int[][] points, int l, int r){
        int[] pivot = points[r];
        int i = l;
        for(int j=i; j<r; ++j){
            if(isCloserOrEqual(points[j], pivot)){
                swap(points, i, j);
                i++;
            }
        }
        swap(points, i, r);
        return i;
    }
    void select(int[][] points, int l, int r, int k){
        if(l>=r) return;
        int p = partition(points, l, r);
        if(p<k){
            select(points, p+1, r, k);
        }else{
            select(points, l, p-1, k);
        }
    }
    public int[][] kClosest(int[][] points, int K) {
        select(points, 0, points.length-1, K);
        return Arrays.copyOfRange(points, 0, K);
    }
}

A good explanation

LIKE CODING

Thursday, May 16, 2019

LeetCode [973] K Closest Points to Origin

No comments:

Post a Comment