We have a list of points that are points on the plane. I want to find K points that are closest to the origin (0, 0). (Here, the distance between two points on the plane is the Euclidean distance.)

You can return the answers in any order. The answer is guaranteed to be unique except for the order of the point coordinates.

Example 1:

Points = [[1,3],[-2,2]], K = 1 The distance between (1, 3) and the origin is SQRT (10), and the distance between (-2, 2) and the origin is SQRT (8), and since SQRT (8) is less than SQRT (10), (-2, 2) is closer to the origin. We only need the nearest K = 1, so the answer is [[-2,2]].Copy the code

Example 2:

Input: points = [[3, 3], [5, 1], [2, 4]], K = 2 output: [[3, 3], [2, 4]] (answer [[- 2, 4], [3]] will be accepted.)Copy the code

Tip:

1 <= K <= points.length <= 10000

-10000 < points[i][0] < 10000

-10000 < points[i][1] < 10000

The simplest method is to sort the square of the Euclidean distance from each point to the origin from the smallest to the largest, and then take out the first K. If the sorting method is used, the time complexity is O(nlogn). There’s actually some room for optimization here, so we can use the heapsort idea and use the PriorityQueue to reduce the time complexity, which is O(nlogk), as shown here

public int[][] kClosest(int[][] points, int K) { PriorityQueue<int[]> pq = new PriorityQueue<>( new Comparator<int[]>() { @Override public int compare(int[] array1, int[] array2) { return array2[0] - array1[0]; }}); for(int i=0; i<K; i++){ pq.offer(new int[]{points[i][0]*points[i][0] + points[i][1]*points[i][1], i}); } for(int i=K; i<points.length; i++){ int dist = points[i][0]*points[i][0] + points[i][1]*points[i][1]; if(dist < pq.peek()[0]){ pq.poll(); pq.offer(new int[]{dist, i}); } } int[][] ans = new int[K][2]; for (int i = 0; i < K; ++i) { ans[i] = points[pq.poll()[1]]; } return ans; }Copy the code