优先级队列
解题思路
维护一个长度为 k 的大顶堆
- 如果堆的元素个数不足 k 个，就可以直接插入堆中；
- 如果堆的元素个数等于 k 个，则检查堆顶与当前出现次数的大小；如果堆顶更大，则舍弃当前值；否则就弹出堆顶，并将当前值插入堆中；
遍历完成后，堆中的元素就是 最接近原点的 K 个点；
复杂度
-
时间复杂度：
O(nlogk)，其中 n 是数组的长度，弹出和插入操作的单次时间复杂度均为 O(logk) -
空间复杂度：
O(k)，因为大根堆中最多有 k 个点；
代码实现
var kClosest = function (points, k) {
let minHeap = new Heap((a, b) => a[0] ** 2 + a[1] ** 2 > b[0] ** 2 + b[1] ** 2);
points.forEach(([x, y], inx) => {
if (inx < k) {
minHeap.push([x, y]);
} else if (Math.abs(minHeap.peek()[0]) ** 2 + Math.abs(minHeap.peek()[1]) ** 2 > x ** 2 + y ** 2) {
minHeap.pop();
minHeap.push([x, y]);
}
});
return minHeap.data;
};
class Heap {
constructor(compare) {
this.arr = [0]; // 忽略 0 这个索引,方便计算左右节点
this.compare = compare ? compare : (a, b) => a > b; // 默认是大顶堆
}
get data() {
return this.arr.slice(1);
}
get size() {
return this.arr.length - 1;
}
// 新增元素
push(item) {
this.arr.push(item);
this.shiftUp(this.arr.length - 1);
}
// 元素上浮，k 是索引
shiftUp(k) {
let { arr, compare, parent } = this;
// 当前元素 > 父元素，则进行交换
while (k > 1 && compare(arr[k], arr[parent(k)])) {
this.swap(parent(k), k);
k = parent(k); // 更新 k 的位置为父元素的位置（交换了位置）
}
}
// 弹出堆顶
pop() {
if (this.arr.length == 1) return null;
this.swap(1, this.arr.length - 1);// 将结尾元素和堆顶元素交换位置
let head = this.arr.pop(); // 删除堆顶
this.sinkDown(1); // 再做下沉操作
return head;
}
// 元素下沉
sinkDown(k) {
let { arr, compare, left, right, size } = this;
while (left(k) <= size) {
// 1. 拿到左右节点的最大值
let child = left(k);
if (right(k) <= size && compare(arr[right(k)], arr[child])) {
child = right(k);
}
// 2. k 满足大顶堆或小顶堆，什么都不做
if (compare(arr[k], arr[child])) {
return;
}
// 3. 交换位置后，继续下沉操作
this.swap(k, child);
k = child; // 更新位置
}
}
// 获取堆顶元素
peek() {
return this.arr[1];
}
// 获取左边元素节点
left(k) {
return k * 2;
}
// 获取右边元素节点
right(k) {
return k * 2 + 1;
}
// 获取父节点
parent(k) {
return Math.floor(k >> 1);
}
// i、j 交换位置
swap(i, j) {
[this.arr[i], this.arr[j]] = [this.arr[j], this.arr[i]];
}
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 451. 根据字符出现频率排序
上一篇
评论
