题目:
Given an array of points
where points[i] = [xi, yi]
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., √(x1 - x2)2 + (y1 - y2)2
).
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]] Explanation: The answer [[-2,4],[3,3]] would also be accepted.
题解:
//参考kanishkmewal
class Solution {
public int[][] kClosest(int[][] points, int k) {
int lo = 0;
int hi = points.length - 1;
int pivotIdx = -1;
// 寻找前k个最近的
while (pivotIdx != k - 1) {
// 返回本次排序好的位置
pivotIdx = partition(points, lo, hi);
// 检查位置与K值的关系
if (pivotIdx < k) {
lo = pivotIdx + 1;
} else {
hi = pivotIdx - 1;
}
}
return Arrays.copyOfRange(points, 0, k);
}
private int partition(int[][] points, int lo, int hi) {
double pivotDist = dist(points[hi]);
int j = lo;
for (int i = lo, k = hi; j < k; ) {
double dist = dist(points[j]);
if (dist < pivotDist) {
swap(points, i++, j++);
} else if (dist > pivotDist) {
swap(points, --k, j);
} else {
j++;
}
}
swap(points, j, hi);
return j;
}
private double dist(int[] p) {
return p[0] * p[0] + p[1] * p[1];
}
private void swap(int[][] points, int i, int j) {
int[] tmp = points[i];
points[i] = points[j];
points[j] = tmp;
}
}
思路:
quickSelect