973. K Closest Points to Origin

Question

Given an array of points where points[i] = [x<sub>i</sub>, y<sub>i</sub>] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x<sub>1</sub><span> </span>- x<sub>2</sub>)<sup>2</sup><span> </span>+ (y<sub>1</sub><span> </span>- y<sub>2</sub>)<sup>2</sup>).

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

Solution

此题可以采用快速排序的思想。可以在O(n)时间复杂度里完成排序。

Solution 2

优先级队列，根据每个点距离的平方排序。时间复杂度O(nlogk)。

Code

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] ret = new int[k][2];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> squaredDistance(a) - squaredDistance(b));
        for(int[] point : points){
            pq.add(point);
        }
        for(int i = 0; i < k; i++){
            ret[i] = pq.poll();
        }
        return ret;
    }
    
    private int squaredDistance(int[] point){
        int x = point[0], y = point[1];
        return x * x + y * y;
    }
}

Solution 3

直接排序。时间复杂度为O(nlogn)。

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] ret = new int[k][2];
        Arrays.sort(points, (a, b) -> squaredDistance(a) - squaredDistance(b));
        for(int i = 0; i < k; i++){
            ret[i] = points[i];
        }
        return ret;
    }
    
    private int squaredDistance(int[] point){
        int x = point[0], y = point[1];
        return x * x + y * y;
    }
}