优先级队列
解题思路
先遍历数组并统计每个字符出现的次数；
维护一个长度为 k 的 小顶堆；
- 如果堆的元素个数不足 k 个，就可以直接插入堆中；
- 如果堆的元素个数等于 k 个，则检查堆顶与当前出现次数的大小；如果堆顶更大，则舍弃当前值；否则就弹出堆顶，并将当前值插入堆中；
遍历完成后，堆中的元素就代表了「出现次数数组」中前 k 大的值；
图解
复杂度
-
时间复杂度：
O(Nlogk)，其中 N 为数组的长度；- 首先遍历原数组，并使用哈希表记录出现次数，共需
O(N)的时间； - 由于堆的大小至多为 k ，因此每次堆操作需要
O(logk)的时间，共需O(Nlogk)的时间；
- 首先遍历原数组，并使用哈希表记录出现次数，共需
-
空间复杂度：
O(N)，哈希表的大小为O(N)，而堆的大小为O(k)
代码实现
var topKFrequent = function (nums, k) {
let map = {};
nums.map(num => {
map[num] = (map[num] || 0) + 1;
})
// 维护一个大小是 K 的小顶堆
let heap = new Heap((a, b) => map[a] < map[b]);
Object.keys(map).forEach((num, inx) => {
if (inx < k) {
heap.push(num);
} else if (map[heap.peek()] < map[num]) {
heap.arr[1] = num;
heap.sinkDown(1);
// heap.push(num);
// heap.pop();
}
})
return heap.arr.slice(1);
};
class Heap {
constructor(compare) {
this.arr = [0]; // 忽略 0 这个索引,方便计算左右节点
this.compare = compare ? compare : (a, b) => a > b; // 默认是大顶堆
}
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🧑💻 146. LRU 缓存
上一篇
评论
