大顶堆
解题思路
维护一个降序的序列，删除前 k - 1 项，队首就是第 k 大的元素，具体实现如下；
维护一个 nums.length 长度的大顶堆，在构建的同时会自动排序；
只要删除 k - 1 个元素即可，此时堆顶元素就是第 K 大的元素；
复杂度
-
时间复杂度：
O(NlogN)，其中遍历数据O(N)，堆内元素调整O(logN) -
空间复杂度：
O(N)
代码实现
var findKthLargest = function (nums, k) {
// 维护一个大小是 nums.length 的大顶堆
let minHeap = new Heap((a, b) => a > b)
for (let num of nums) {
minHeap.push(num)
}
while (k-- > 1) {
minHeap.pop() // 删除前 k-1 项
}
return minHeap.peek()
};
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]];
}
}
小顶堆
解题思路
维护一个降序的序列，删除前 nums.length - k 项，队首就是第 k 大的元素，具体实现如下；
可以构建一个长度为 K 的最小堆；
- 如果当前堆不满，直接添加；
- 堆满的时候，先添加后删除堆顶元素（添加、删除均会进行排序），保证 K 个元素大小；
复杂度
-
时间复杂度：
O(NlogK)，遍历数据O(N)，堆内元素调整O(logK) -
空间复杂度：
O(K)
代码实现
var findKthLargest = function (nums, k) {
// 维护一个大小是 K 的小顶堆
let minHeap = new Heap((a, b) => a < b)
for (let num of nums) {
minHeap.push(num)
if (minHeap.size > k) { // 删除 nums.length - k 项
minHeap.pop()
}
}
return minHeap.peek()
};
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🧑💻 295. 数据流的中位数
上一篇
评论
