# 0973. K Closest Points to Origin
###### tags: `Leetcode` `Medium` `QuickSort` `FaceBook`
Link: https://leetcode.com/problems/k-closest-points-to-origin/
## 思路
### 思路一
暴力排序
### 思路二
Priority Queue
### 思路三
Quick Sort
## Code
### 思路一 O(NlogN) & O(logN)

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] point1, int[] point2) {
                return (point1[0] * point1[0] + point1[1] * point1[1]) - (point2[0] * point2[0] + point2[1] * point2[1]);
            }
        });
        return Arrays.copyOfRange(points, 0, k);
    }
}

### 思路二 O（Nlogk) & O(k) (大根堆里有k个点)

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (b[0]*b[0]+b[1]*b[1]-a[0]*a[0]-a[1]*a[1]));
        for(int i = 0;i < points.length;i++){
            if(pq.size()<k){
                pq.offer(points[i]);
            }
            else if(pq.comparator().compare(points[i],pq.peek())>0){
                pq.poll();
                pq.offer(points[i]);
            }
        }
        int[][] res = new int[pq.size()][2];
        int idx = 0;
        for(int[] point:pq){
            res[idx++] = point;
        }
        return res;
    }
}

### 思路三 （期望为 O(N) & O(logN)）

class Solution {
    static Random rand = new Random();
    public int[][] kClosest(int[][] points, int k) {
        int n = points.length;
        randomSelect(points, 0, n-1, k);
        return Arrays.copyOfRange(points, 0,k);
    }
    public static void randomSelect(int[][] points, int left, int right, int k){
        int pivotId = left + rand.nextInt(right - left + 1);
        int pivot = points[pivotId][0] * points[pivotId][0] + points[pivotId][1] * points[pivotId][1];
        swap(points, right, pivotId);
        int i = left - 1;
        for (int j = left; j < right; ++j) {
            int dist = points[j][0] * points[j][0] + points[j][1] * points[j][1];
            if (dist <= pivot) {
                ++i;
                swap(points, i, j);
            }
        }
        ++i;
        swap(points, i, right);
        // [left, i-1] 都小于等于 pivot, [i+1, right] 都大于 pivot
        if (k < i - left + 1) {
            randomSelect(points, left, i - 1, k);
        } else if (k > i - left + 1) {
            randomSelect(points, i + 1, right, k - (i - left + 1));
        }
    }

    public static int computeDist(int[][] points, int index){
        return points[index][0]*points[index][0]+points[index][1]*points[index][1];
    }
    public static void swap(int[][] points, int a, int b){
        int[] temp = points[a];
        points[a] = points[b];
        points[b]  = temp;
    }
}

## Result
### 思路一
Runtime: 15 ms, faster than **82.60%** of Java online submissions for K Closest Points to Origin.
Memory Usage: 47.3 MB, less than **88.53%** of Java online submissions for K Closest Points to Origin.
### 思路二
Runtime: 3 ms, faster than **98.69%** of Java online submissions for K Closest Points to Origin.
Memory Usage: 47.7 MB, less than **63.94%** of Java online submissions for K Closest Points to Origin.