跳至主要內容

973. K Closest Points to Origin

973. K Closest Points to Originopen in new window

🟠   🔖  几何 数组 数学 分治 快速选择 排序 堆（优先队列）  🔗 LeetCodeopen in new window

题目

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.

Constraints:

  • 1 <= k <= points.length <= 10^4
  • -10^4 <= xi, yi <= 10^4

题目大意

给定一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。

这里，平面上两点之间的距离是 欧几里德距离（ √(x1 - x2)2 + (y1 - y2)2 ）。

你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案 确保 是 唯一 的。

解题思路

这道题是 Top K 问题的变种，求的是最小的 K 个数，可以用大小为 K 的大顶堆来解决。

  1. 遍历题目提供的 points，求出每个点到原点的距离 dist；
  2. 将点和距离 [point, dist] 添加到大顶堆中，拿 dist 与堆顶的元素对比:
    • 如果比堆顶元素小，就把堆顶元素删除，并且将这个元素插入到堆中；
    • 如果比堆顶元素大，则不做处理；
  3. 遍历完之后，返回大顶堆中的 K 个点。

代码

/**
 * @param {number[][]} points
 * @param {number} k
 * @return {number[][]}
 */
var kClosest = function (points, k) {
  let heap = [];
  const add = ([point, dist]) => {
    if (heap.length < k) {
      heap.push([point, dist]);
      heapifyUp(heap.length - 1);
    } else if (heap[0][1] > dist) {
      heap[0] = [point, dist];
      heapifyDown(0);
    }
  };
  const heapifyUp = (i) => {
    while (i) {
      const parent = Math.floor((i - 1) / 2);
      if (heap[i][1] > heap[parent][1]) {
        [heap[i], heap[parent]] = [heap[parent], heap[i]];
        i = parent;
      } else {
        break;
      }
    }
  };
  const heapifyDown = (i) => {
    const left = i * 2 + 1;
    const right = i * 2 + 2;
    let max = i;
    if (left < heap.length && heap[left][1] > heap[max][1]) {
      max = left;
    }
    if (right < heap.length && heap[right][1] > heap[max][1]) {
      max = right;
    }
    if (max !== i) {
      [heap[i], heap[max]] = [heap[max], heap[i]];
      heapifyDown(max);
    }
  };
  for (let point of points) {
    const dist = point[0] * point[0] + point[1] * point[1];
    add([point, dist]);
  }
  return heap.map((item) => item[0]);
};

相关题目

相关题目
- [215. 数组中的第 K 个最大元素](https://leetcode.com/problems/kth-largest-element-in-an-array)
- [347. 前 K 个高频元素](https://leetcode.com/problems/top-k-frequent-elements)
- [692. 前 K 个高频单词](https://leetcode.com/problems/top-k-frequent-words)
- [1779. 找到最近的有相同 X 或 Y 坐标的点](https://leetcode.com/problems/find-nearest-point-that-has-the-same-x-or-y-coordinate)
Copyright © 2024 2xiao