973. 最接近原点的 K 个点

🟠   🔖  几何 数组 数学 分治 快速选择 排序 堆（优先队列）  🔗 力扣 LeetCode

题目

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个最大元素	[✓]	数组 分治 快速选择 2+
347	前 K 个高频元素	[✓]	数组 哈希表 分治 5+
692	前K个高频单词		字典树 哈希表 字符串 4+
1779	找到最近的有相同 X 或 Y 坐标的点		数组
3111	覆盖所有点的最少矩形数目		贪心 数组 排序
3275	第 K 近障碍物查询		数组 堆（优先队列）