Comment on page

973.K-Closest-Points-to-Origin

973. K Closest Points to Origin

题目地址

题目描述

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.)

代码

Approach 1: Sort

class Solution {
public int[][] kClosest(int[][] points, int K) {
int N = points.length;
int[] dists = new int[N];
for (int i = 0; i < N; i++) {
dists[i] = dist(points[i]);
}
​
Arrays.sort(dists);
int distK = dists[k - 1];
​
int[][] ans = new int[K][2];
int t = 0;
for (int i = 0; i < N; i++) {
if (dist(points[i]) <= distK) {
ans[t++] = points[i];
}
}
return ans;
}
​
public int dist(int[] point) {
return point[0] * point[0] + point[1] * point[1];
}
​
}

Approach 2: max-Heap

public int[][] kClosest(int[][] points, int K) {
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((p1, p2) -> p2[0] * p2[0] + p2[1] * p2[1] - p1[0] * p1[0] - p1[1] * p1[1]);
for (int[] p : points) {
pq.offer(p);
if (pq.size() > K) {
pq.poll();
}
}
int[][] res = new int[K][2];
while (K > 0) {
res[--K] = pq.poll();
}
return res;
}

Approach 3: Quick sort

the average time complexity is O(N) , but just like quick sort, in the worst case, this solution would be degenerated to O(N^2), and pratically, the real time it takes on leetcode is 15ms.
public int[][] kClosest(int[][] points, int K) {
int len = points.length, l = 0, r = len - 1;
while (l <= r) {
int mid = helper(points, l, r);
if (mid == K) break;
if (mid < K) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return Arrays.copyOfRange(points, 0, K);
}
​
private int helper(int[][] A, int l, int r) {
int[] pivot = A[l];
while (l < r) {
while (l < r && compare(A[r], pivot) >= 0) r--;
A[l] = A[r];
while (l < r && compare(A[l], pivot) <= 0) l++;
A[r] = A[l];
}
A[l] = pivot;
return l;
}
​
private int compare(int[] p1, int[] p2) {
return p1[0] * p1[0] + p1[1] * p1[1] - p2[0] * p2[0] - p2[1] * p2[1];
}