「每日LeetCode」2020年11月9日

本文最后更新于：2023年3月19日 晚上

Lt973. 最接近原点的 K 个点

973. 最接近原点的 K 个点

我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
（这里，平面上两点之间的距离是欧几里德距离。）
你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。
 示例 1：

1
2
3
4
5
6
7
输入：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：

1
2
3
输入：points = [[3,3],[5,-1],[-2,4]], K = 2
输出：[[3,3],[-2,4]]
（答案 [[-2,4],[3,3]] 也会被接受。）

提示：

  1. 1 <= K <= points.length <= 10000
  2. -10000 < points[i][0] < 10000
  3. -10000 < points[i][1] < 10000

思路

排序

把数组按照据原点距离升序排序，取前 K 个元素即可

模拟快排

模拟快排，快排有一个性质，一次快排确定的点，左边的数组一定比当前的点小。所以：
当当前点为 K 即左边有 K 个元素时，题目所需要的解就已经求出来了，不需要继续进行排序。
当当前点比 K 大，说明左边元素大于 K 个，需要对左边继续进行排序。当当前点比 K 小，说明左边元素小于 K 个，需要对右边继续进行排序。

解答

排序

1
2
3
4
5
6
7
8
9
/**
 * @param {number[][]} points
 * @param {number} K
 * @return {number[][]}
 */
var kClosest = function (points, K) {
  points.sort((a, b) => a[0] ** 2 + a[1] ** 2 - (b[0] ** 2 + b[1] ** 2));
  return points.splice(0, K);
};

模拟快排

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
/**
 * @param {number[][]} points
 * @param {number} K
 * @return {number[][]}
 */
var kClosest = function (points, K) {
  const getValue = (point) => point[0] ** 2 + point[1] ** 2;
  const quickSort = (start, end) => {
    let left = start,
      right = end;
    while (left < right) {
      while (left < right && getValue(points[right]) >= getValue(points[start]))
        right--;
      while (left < right && getValue(points[left]) <= getValue(points[start]))
        left++;
      [points[left], points[right]] = [points[right], points[left]];
    }
    [points[start], points[left]] = [points[left], points[start]];
    // console.log(left)
    if (left === K) {
      return;
    } else if (left < K) {
      quickSort(left + 1, end);
    } else {
      quickSort(start, left - 1);
    }
  };
  quickSort(0, points.length - 1);
  return points.slice(0, K);
};