K Closest Points to Origin（最接近原点的 K 个点）

题目 / Problem

中文： 给定一个点数组 points，其中 points[i] = [xᵢ, yᵢ] 表示 X-Y 平面上的一个点；另给一个整数 k。请返回距离原点 (0, 0) 最近的 k 个点。

平面上两点之间使用欧几里得距离。答案可以按任意顺序返回，并且除顺序外，答案保证唯一。

English: Given an array points, where points[i] = [xᵢ, yᵢ] 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 is their Euclidean distance. You may return the answer in any order. The answer is guaranteed to be unique except for its order.

距离公式 / Distance Formula

点 (x, y) 到原点的欧几里得距离为：
The Euclidean distance from (x, y) to the origin is:

distance = √(x² + y²)

平方根函数严格递增，因此比较距离时，只需比较平方距离：
Because the square-root function is strictly increasing, comparing squared distances is sufficient:

distanceSquared = x² + y²

这样既能得到相同的远近顺序，也避免了不必要的 Math.sqrt() 计算和浮点数。
This preserves the same ordering while avoiding unnecessary Math.sqrt() calls and floating-point values.

示例 / Examples

Example 1

坐标平面上的两个点 / Two points on the coordinate plane

Input:  points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]

(1, 3)   的平方距离 / squared distance = 1² + 3² = 10
(-2, 2)  的平方距离 / squared distance = (-2)² + 2² = 8

因为 8 < 10，点 (-2, 2) 更接近原点。只需要最近的一个点，因此返回 [[-2,2]]。
Because 8 < 10, (-2, 2) is closer to the origin. Since k = 1, return [[-2,2]].

Example 2

Input:  points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]

(3, 3)   → 18
(5, -1)  → 26
(-2, 4)  → 20

平方距离最小的两个点是 (3, 3) 和 (-2, 4)。返回 [[-2,4],[3,3]] 也同样正确。
The two smallest squared distances belong to (3, 3) and (-2, 4). Returning [[-2,4],[3,3]] is also valid.

约束 / Constraints

1 <= k <= points.length <= 10⁴
-10⁴ <= xᵢ, yᵢ <= 10⁴

解题思路：维护大小为 K 的最大堆 / Approach: Max Heap of Size K

遍历所有点，并维护一个最多包含 k 个元素的最大堆。堆顶始终是当前选中点中距离原点最远的一个。
Traverse all points while maintaining a max heap containing at most k entries. The heap root is always the farthest among the currently selected points.

对于每个点：
For every point:

计算它到原点的平方距离。
Calculate its squared distance from the origin.
将点和距离加入最大堆。
Add the point and distance to the max heap.
如果堆中元素数量超过 k，弹出堆顶，也就是当前最远的点。
If the heap grows beyond k, remove its root—the currently farthest point.

遍历结束后，堆中恰好保留全局距离最小的 k 个点。
After traversal, the heap contains exactly the globally closest k points.

JavaScript 实现 / JavaScript Implementation

JavaScript 没有内置优先队列，下面使用数组实现一个简单的最大堆：
JavaScript has no built-in priority queue, so the following solution implements a small max heap with an array:

/**
 * @param {number[][]} points
 * @param {number} k
 * @return {number[][]}
 */
function kClosest(points, k) {
  const heap = [];

  function swap(i, j) {
    [heap[i], heap[j]] = [heap[j], heap[i]];
  }

  function push(entry) {
    heap.push(entry);
    let index = heap.length - 1;

    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);

      if (heap[parent].distance >= heap[index].distance) {
        break;
      }

      swap(parent, index);
      index = parent;
    }
  }

  function popMax() {
    const last = heap.pop();

    if (heap.length === 0) {
      return;
    }

    heap[0] = last;
    let index = 0;

    while (true) {
      const left = index * 2 + 1;
      const right = index * 2 + 2;
      let largest = index;

      if (
        left < heap.length &&
        heap[left].distance > heap[largest].distance
      ) {
        largest = left;
      }

      if (
        right < heap.length &&
        heap[right].distance > heap[largest].distance
      ) {
        largest = right;
      }

      if (largest === index) {
        break;
      }

      swap(index, largest);
      index = largest;
    }
  }

  for (const point of points) {
    const [x, y] = point;
    push({ point, distance: x * x + y * y });

    if (heap.length > k) {
      popMax();
    }
  }

  return heap.map((entry) => entry.point);
}

题目允许答案按任意顺序返回，因此无需对堆中最后的 k 个点重新排序。
The answer may be returned in any order, so the final k heap entries do not need to be sorted.

执行过程 / Walkthrough

以 points = [[3,3],[5,-1],[-2,4]]、k = 2 为例：
For points = [[3,3],[5,-1],[-2,4]] and k = 2:

当前点 / Point	平方距离 / Squared Distance	加入后的距离 / After Push	超过 K 后 / After Trimming
`[3,3]`	18	`{18}`	`{18}`
`[5,-1]`	26	`{26, 18}`	`{26, 18}`
`[-2,4]`	20	`{26, 18, 20}`	弹出 26，保留 `{20, 18}` / Remove 26

最终保留平方距离为 18 和 20 的点，即 [[3,3],[-2,4]]。
The remaining points have squared distances 18 and 20, giving [[3,3],[-2,4]].

最大堆复杂度 / Max-Heap Complexity

设点的数量为 n。
Let n be the number of points.

时间复杂度：O(n log k)，每个点最多执行一次大小不超过 k + 1 的堆插入和删除。
Time: O(n log k), because each point performs at most one insertion and removal on a heap of size at most k + 1.
空间复杂度：O(k)，堆中最多保留 k + 1 个元素。
Space: O(k), because the heap holds at most k + 1 entries.

当 k 远小于 n 时，最大堆比对全部点排序更高效。
When k is much smaller than n, the max heap is more efficient than sorting every point.

简单排序解法 / Simple Sorting Approach

最直接的做法是按平方距离对所有点排序，再取前 k 个：
The most direct solution sorts all points by squared distance and takes the first k:

function kClosestBySorting(points, k) {
  return points
    .slice()
    .sort((pointA, pointB) => {
      const distanceA = pointA[0] ** 2 + pointA[1] ** 2;
      const distanceB = pointB[0] ** 2 + pointB[1] ** 2;
      return distanceA - distanceB;
    })
    .slice(0, k);
}

使用 slice() 复制数组，避免排序修改原始 points。
slice() copies the array so sorting does not modify the original points.

时间复杂度 / Time: O(n log n)
空间复杂度 / Space: O(n)，复制数组需要额外空间，排序本身的空间还取决于实现。
Copying the array requires O(n) extra space; the sort may require additional implementation-dependent space.

排序解法代码最短，最大堆则将时间优化为 O(n log k)。
The sorting solution is shortest, while the max heap improves the running time to O(n log k).

Quickselect 解法 / Quickselect Approach

Quickselect 使用与快速排序相似的分区操作，将距离小的点移动到数组左侧，直到前 k 个位置包含答案。其平均时间复杂度为 O(n)，但最坏情况下为 O(n²)。
Quickselect uses a partition operation similar to quicksort, moving closer points to the left until the first k positions contain the answer. Its average time is O(n), with a worst case of O(n²).

function kClosestQuickselect(points, k) {
  const result = points.slice();
  const distance = ([x, y]) => x * x + y * y;

  function partition(left, right) {
    const pivotDistance = distance(result[right]);
    let boundary = left;

    for (let index = left; index < right; index++) {
      if (distance(result[index]) <= pivotDistance) {
        [result[index], result[boundary]] = [result[boundary], result[index]];
        boundary++;
      }
    }

    [result[boundary], result[right]] = [result[right], result[boundary]];
    return boundary;
  }

  let left = 0;
  let right = result.length - 1;

  while (left <= right) {
    const pivotIndex = partition(left, right);

    if (pivotIndex === k - 1) {
      break;
    }

    if (pivotIndex < k - 1) {
      left = pivotIndex + 1;
    } else {
      right = pivotIndex - 1;
    }
  }

  return result.slice(0, k);
}

平均时间复杂度 / Average Time: O(n)
最坏时间复杂度 / Worst-Case Time: O(n²)
额外空间复杂度 / Extra Space: O(n)，此实现先复制输入数组；若允许原地修改则辅助空间为 O(1)。
This implementation copies the input; if in-place modification is allowed, auxiliary space is O(1).

方案对比 / Approach Comparison

方法 / Method	时间 / Time	额外空间 / Extra Space	特点 / Notes
排序 / Sorting	`O(n log n)`	`O(n)`（本实现）	最简单 / Simplest
大小为 K 的最大堆 / Max Heap	`O(n log k)`	`O(k)`	`k` 较小时合适 / Good when `k` is small
Quickselect	平均 `O(n)`	`O(n)`（本实现）	平均最快，但最坏 `O(n²)` / Fast average; quadratic worst case

易错点 / Common Pitfalls

比较平方距离即可，不需要调用 Math.sqrt()。
Compare squared distances; Math.sqrt() is unnecessary.
最大堆的堆顶应是当前保留点中最远的点，超出 k 时将它删除。
The max-heap root must be the farthest retained point, which is removed when the heap exceeds k.
返回的是点坐标数组，不是距离数组。
Return point coordinates, not their distances.
答案可以按任意顺序返回，无需额外排序。
The answer can be returned in any order, so no final sorting is required.
JavaScript 的 sort() 会修改原数组；若要保留输入，应先复制。
JavaScript's sort() mutates the array; copy it first if the input must be preserved.
坐标可能为负数，但平方后仍为非负数，不影响距离比较。
Coordinates may be negative, but their squares are nonnegative and compare correctly.

K Closest Points to Origin