https://leetcode.com/problems/k-closest-points-to-origin/
https://leetcode.com/problems/k-closest-points-to-origin/discuss/217969/Java-8-liner-using-PriorityQueue-O(nlogK).
X. Sort the points by distance, then take the closest K points.
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
- Put the points into a PriorityQueue, and the order is by their distance to origin
descendingly; - Whenever the size reach K + 1, poll the farthest point out.
public int[][] kClosest(int[][] points, int K) {
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(a -> -a[0] * a[0] - a[1] * a[1]));
for (int[] p : points) {
pq.offer(p);
if (pq.size() > K) { pq.poll(); } // poll out the farthest among the K + 1 points.
}
int[][] ans = new int[K][2];
while (K-- > 0) { ans[K] = pq.poll(); }
return ans;
}
The last solution is based on quick sort, we can also call it quick select. In the quick sort, we will always choose a pivot to compare with other elements. After one iteration, we will get an array that all elements smaller than the pivot are on the left side of the pivot and all elements greater than the pivot are on the right side of the pviot (assuming we sort the array in ascending order). So, inspired from this, each iteration, we choose a pivot and then find the position p the pivot should be. Then we compare p with the K, if the p is smaller than the K, meaning the all element on the left of the pivot are all proper candidates but it is not adequate, we have to do the same thing on right side, and vice versa. If the p is exactly equal to the K, meaning that we've found the K-th position. Therefore, we just return the first K elements, since they are not greater than the pivot.
Theoretically, 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.
The advantage of this solution is it is very efficient.
The disadvatage of this solution are it is neither an online solution nor a stable one. And the first K elements are not sorted in ascending order.
The disadvatage of this solution are it is neither an online solution nor a stable one. And the first K elements are not sorted in ascending order.
The short code shows as follows:
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];
}
Let's do the
work(i, j, K) of partially sorting the subarray (points[i], points[i+1], ..., points[j]) so that the smallest K elements of this subarray occur in the first K positions (i, i+1, ..., i+K-1).
First, we quickselect by a random pivot element from the subarray. To do this in place, we have two pointers
i and j, and move these pointers to the elements that are in the wrong bucket -- then, we swap these elements.
After, we have two buckets
[oi, i] and [i+1, oj], where (oi, oj) are the original (i, j) values when calling work(i, j, K). Say the first bucket has 10 items and the second bucket has 15 items. If we were trying to partially sort say, K = 5 items, then we only need to partially sort the first bucket: work(oi, i, 5). Otherwise, if we were trying to partially sort say, K = 17 items, then the first 10 items are already partially sorted, and we only need to partially sort the next 7 items: work(i+1, oj, 7).
int[][] points;
public int[][] kClosest(int[][] points, int K) {
this.points = points;
work(0, points.length - 1, K);
return Arrays.copyOfRange(points, 0, K);
}
public void work(int i, int j, int K) {
if (i >= j)
return;
int oi = i, oj = j;
int pivot = dist(ThreadLocalRandom.current().nextInt(i, j));
while (i < j) {
while (i < j && dist(i) < pivot)
i++;
while (i < j && dist(j) > pivot)
j--;
swap(i, j);
}
if (K <= i - oi + 1)
work(oi, i, K);
else
work(i + 1, oj, K - (i - oi + 1));
}
public int dist(int i) {
return points[i][0] * points[i][0] + points[i][1] * points[i][1];
}
public void swap(int i, int j) {
int t0 = points[i][0], t1 = points[i][1];
points[i][0] = points[j][0];
points[i][1] = points[j][1];
points[j][0] = t0;
points[j][1] = t1;
}
X. Sort the points by distance, then take the closest K points.
