解题步骤
- 构建一个最小堆,并依次把数据的值插入堆中
- 当堆的容量超过 K,就删除堆顶
- 插入结束后,堆顶就是第 K 个最大的元素
通过最小堆的方式实现
- 时间复杂度:O (n * logk)
空间复杂度:O (k)
function findKthLargest(nums, k) {
const h = new MinHeap();
nums.forEach((n) => {
h.insert(n);
if (h.size() > k) {
h.pop();
}
});
return h.top();
}
在代码中只存在一个 for 循环,但是在循环体内有个 insert 和 pop,他们的时间复杂度分别是 logk,所以上方代码的时间复杂度为 O (n * logk) 。而空间复杂度是 O (k),因为主要用了一个数据结构堆进行存储元素,而元素的最大数量则是由 k 决定。