只实现了一些基础的函数
class MaxHeadp {
heap
border
constructor(nums) {
this.heap = nums;
this.border = nums.length - 1
this.initHeap();
}
initHeap() {
const endIndex = this.getTopNode(this.border)
for (let index = endIndex; index >= 0; index--) {
this.downNode(index)
}
}
haveNum() {
return this.border + 1
}
pop() {
if (this.border === -1) {
return undefined
}
const temp = this.heap[0];
this.heap[0] = this.heap[this.border];
this.border--;
this.downNode(0)
return temp
}
swap(x, y) {
let temp = this.heap[x]
this.heap[x] = this.heap[y]
this.heap[y] = temp
}
downNode(index) {
let left = this.getLeftNode(index);
let right = this.getRightNode(index);
while (left <= this.border || right <= this.border) {
let maxIndex = undefined
if (left <= this.border || right <= this.border) {
maxIndex = this.heap[left] < this.heap[right] ? right : left
} else {
maxIndex = left <= this.border ? right : left
}
if (this.heap[index] < this.heap[maxIndex]) {
this.swap(index, maxIndex)
index = maxIndex
left = this.getLeftNode(index);
right = this.getRightNode(index);
} else {
break;
}
}
}
getTopNode(index) {
return Math.floor((index - 1) / 2)
}
getLeftNode(index) {
return (index + 1) * 2 - 1
}
getRightNode(index) {
return (index + 1) * 2
}
}
var findKthLargest = function (nums, k) {
const heap = new MaxHeadp(nums)
let times = 0
let lastNum = undefined
while (heap.haveNum() != 0) {
const num = heap.pop()
if (num !== lastNum) {
times++
}
if (times == k) {
return num
}
}
return -1
};
置顶卡
沉默卡
照妖镜