Java&Go-LeetCode973. 最接近原点的 K 个点-快排 | 最大堆
• 算法
• 1.快排
• 2.每次寻找基准数后判断基准数是否刚好在K-1位置
• 如果在，那么左侧刚好是最小的K个point
• 如果不在，递归寻找
```public int[][] kClosest(int[][] points, int K) {
int left = 0, right = points.length - 1;
int index = partition(points, left, right);
while (index != K - 1) {
if (index < K - 1) {
left = index + 1;
} else {
right = index - 1;
}
index = partition(points, left, right);
}

int[][] result = new int[K][];
for (int i = 0; i < K; i++) {
result[i] = points[i];
}
return result;
}

private int partition(int[][] points, int start, int end) {
int index = new Random().nextInt(end-start+1) + start;
swap(points, index, end);
int small = start - 1;
for (index = start; index < end; index++) {
if (compare(points[index], points[end]) < 0) {
small++;
if (small != index) {
swap(points, small, index);
}
}
}
swap(points, ++small, end);
return small;
}

private void swap(int[][] points, int x, int y) {
int[] temp = points[x];
points[x] = points[y];
points[y] = temp;
}

private int compare(int[] x, int[] y) {
return (x[0]*x[0]+x[1]*x[1]) - (y[0]*y[0]+y[1]*y[1]);
}```
```func kClosest(points [][]int, K int) [][]int {
left, right := 0, len(points) - 1
index := partition(points, left, right)
for index != K - 1 {
if index < K - 1 {
left = index + 1
} else {
right = index - 1
}
index = partition(points, left, right)
}

result := make([][]int, K)
for i := 0; i < K; i++ {
result[i] = points[i]
}
return result
}

func partition(points [][]int, start, end int) int {
rand.Seed(time.Now().Unix())
index := rand.Intn(end-start+1) + start
points[index], points[end] = points[end], points[index]
small := start - 1
for index = start; index < end; index++ {
if compare(points[index], points[end]) < 0 {
small++
if small != index {
points[index], points[small] = points[small], points[index]
}
}
}
points[small+1], points[end] = points[end], points[small+1]
return small+1
}

func compare(point1, point2 []int) int {
return (point1[0]*point1[0]+point1[1]*point1[1]) - (point2[0]*point2[0]+point2[1]*point2[1])
}```
• 算法
• 1.最大堆
• TODO
LeetCode题解 文章被收录于专栏

2022-12-13 19:37

2022-12-03 16:23

2022-12-14 12:44

2022-12-07 21:39

2022-12-10 15:01

2022-12-28 14:56

2022-12-26 18:01

01-15 19:36

01-03 15:27