友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
973. 最接近原点的 K 个点
给定一个数组 points，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，并且是一个整数 k，返回离原点 (0, 0) 最近的 k 个点。
这里，平面上两点之间的距离是 欧几里德距离 \(\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)。
你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案 确保 是 唯一 的。
示例 1：
输入：points = [[1,3],[-2,2]], k = 1 输出：[[-2,2]] 解释： (1, 3) 和原点之间的距离为 sqrt(10)， (-2, 2) 和原点之间的距离为 sqrt(8)， 由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。 我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。
示例 2：
输入：points = [[3,3],[5,-1],[-2,4]], k = 2 输出：[[3,3],[-2,4]] （答案 [[-2,4],[3,3]] 也会被接受。）
提示：
-
1 <= k <= points.length <= 104 -
-104 < xi, yi < 104
思路分析
排序，堆，快速选择等多种解法均可。
| 快速选择写的还是漏洞百出！！ |
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-08-29 21:55:28
*/
public int[][] kClosest(int[][] points, int k) {
quickSelect(points, k - 1, 0, points.length - 1);
return Arrays.copyOfRange(points, 0, k);
}
private void quickSelect(int[][] points, int idx, int left, int right) {
if (left >= right) {
return;
}
int p = partittion(points, left, right);
if (p == idx) {
return;
}
if (p < idx) {
quickSelect(points, idx, p + 1, right);
} else {
quickSelect(points, idx, left, p - 1);
}
}
private int partittion(int[][] points, int left, int right) {
int[] v = points[left];
int dist = v[0] * v[0] + v[1] * v[1];
int l = left, r = right + 1;
while (l <= r) {
while (++l <= right && points[l][0] * points[l][0] + points[l][1] * points[l][1] < dist) {
}
while (left <= --r && points[r][0] * points[r][0] + points[r][1] * points[r][1] > dist) {
}
if (l >= r) {
break;
}
swap(points, l, r);
}
points[left] = points[r];
points[r] = v;
return r;
}
private void swap(int[][] points, int a, int b) {
int[] tmp = points[a];
points[a] = points[b];
points[b] = tmp;
}