703. 数据流中的第 K 大元素
703. 数据流中的第 K 大元素
🟢 🔖 树
设计
二叉搜索树
二叉树
数据流
堆(优先队列)
🔗 力扣
LeetCode
题目
Design a class to find the kth
largest element in a stream. Note that it is the kth
largest element in the sorted order, not the kth
distinct element.
Implement KthLargest
class:
KthLargest(int k, int[] nums)
Initializes the object with the integerk
and the stream of integersnums
.int add(int val)
Appends the integerval
to the stream and returns the element representing thekth
largest element in the stream.
Example 1:
Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]
Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8
Constraints:
1 <= k <= 10^4
0 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
-10^4 <= val <= 10^4
- At most
10^4
calls will be made toadd
. - It is guaranteed that there will be at least
k
elements in the array when you search for thekth
element.
题目大意
设计一个找到数据流中第 k
大元素的类(class)。注意是排序后的第 k
大元素,不是第 k
个不同的元素。
请实现 KthLargest
类:
KthLargest(int k, int[] nums)
使用整数k
和整数流nums
初始化对象。int add(int val)
将val
插入数据流nums
后,返回当前数据流中第k
大的元素
解题思路
可以用小顶堆来做。
数组在不断插入数据,如果每次求前 K
大的数据,都基于当前的数据重新计算的话,那时间复杂度就是 O(nlogK)
,n
表示当前的数据的大小。
可以维护一个大小为 K
的小顶堆,当有数据被添加到数组中时,就拿它与堆顶的元素对比。
- 如果比堆顶元素大,就把堆顶元素删除,并且将这个元素插入到堆中;
- 如果比堆顶元素小,则不做处理;
这样,无论任何时候需要查询当前的前 K
大的数据,都可以立刻返回。
复杂度分析
时间复杂度:
O(log k)
对于
add
方法,最坏情况下,我们需要进行堆化的次数是堆的高度,即log k
。因此,add
方法的时间复杂度是O(log k)
。在初始化时,需要将前k
个元素构建最小堆,这一过程的时间复杂度是O(klog k)
。总体来说,
KthLargest
类的时间复杂度主要受add
方法的影响,为O(log k)
。空间复杂度:
O(k)
。
代码
class KthLargest {
// @param {number} k
// @param {number[]} nums
constructor(k, nums) {
this.k = k;
this.heap = [];
for (let i of nums) {
this.add(i);
}
}
// @param {number} val
// @return {number}
add(val) {
if (this.heap.length < this.k) {
this.heap.push(val);
this.heapifyUp(this.heap.length - 1);
} else if (this.heap[0] < val) {
this.heap[0] = val;
this.heapifyDown(0);
}
return this.heap[0];
}
heapifyUp(index) {
while (index > 0) {
const parent = Math.floor((index - 1) / 2);
if (this.heap[parent] > this.heap[index]) {
[this.heap[parent], this.heap[index]] = [
this.heap[index],
this.heap[parent]
];
index = parent;
} else {
break;
}
}
}
heapifyDown(index) {
const left = 2 * index + 1;
const right = 2 * index + 2;
let min = index;
if (left < this.heap.length && this.heap[left] < this.heap[min]) {
min = left;
}
if (right < this.heap.length && this.heap[right] < this.heap[min]) {
min = right;
}
if (min !== index) {
[this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
this.heapifyDown(min);
}
}
}
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
215 | 数组中的第K个最大元素 | [✓] | 数组 分治 快速选择 2+ | 🟠 | 🀄️ 🔗 |
1825 | 求出 MK 平均值 | 设计 队列 数据流 2+ | 🔴 | 🀄️ 🔗 | |
2102 | 序列顺序查询 | 设计 数据流 有序集合 1+ | 🔴 | 🀄️ 🔗 |