Shinkai005
V1
2022/02/12阅读:41主题:红绯
【leetcode】215.数组中的第K个最大元素
【leetcode】215.数组中的第K个最大元素
题目描述
题目思路
-
看到第K个最大元素 -
那么直接使用最小堆
个人题解
-
构建一个最小堆, 并依次把数组的值插入堆中 -
当发现堆的容量超过K, 就开始删除堆顶. -
插入结束后,堆顶就是第K个最大元素.
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
class MinHeap {
constructor() {
this.heap = [];
}
swap(i1, i2) {
//const temp = this.heap[i1];
//this.heap[i1] = this.heap[i2];
//this.heap[i2] = temp;
[this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
}
getParentIndex(i) {
return Math.floor((i - 1) / 2);
// return (i-1) >> 1; // 老师用的是下面的,但是js位运算比mathAPi慢,所以...
}
shiftUp(index) {
if (index === 0) {
return;
}
const parentIndex = this.getParentIndex(index);
if (this.heap[parentIndex] > this.heap[index]) {
this.swap(parentIndex, index);
this.shiftUp(parentIndex);
}
}
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
getLeftIndex(i) {
return i * 2 + 1;
}
getRightIndex(i) {
return i * 2 + 2;
}
shiftDown(index) {
const leftIndex = this.getLeftIndex(index);
const rightIndex = this.getRightIndex(index);
if (this.heap[leftIndex] < this.heap[index]) {
this.swap(leftIndex, index);
this.shiftDown(leftIndex);
}
if (this.heap[rightIndex] < this.heap[index]) {
this.swap(rightIndex, index);
this.shiftDown(rightIndex);
}
}
pop() {
this.heap[0] = this.heap.pop();
this.shiftDown(0);
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length;
}
}
const findKthLargest = function (nums, k) {
const h = new MinHeap();
nums.forEach(n => {
h.insert(n);
if (h.size() > k) {
h.pop();
}
});
return h.peek();
};
console.log(findKthLargest([3,2,1,5,6,4],2));
时间复杂度(time complexity)
O(nlogk)
foreach是n
里面嵌套了一个insert()方法,是logk量级
空间复杂度(space complexity)
堆大小是k
O(K)
作者介绍
Shinkai005
V1
公众号:深海笔记Shinkai