703.Kth Largest Element in a Stream
703.Kth Largest Element in a Stream
难度:Easy
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.
Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.
1
Example:
2
3
int k = 3;
4
int[] arr = [4,5,8,2];
5
KthLargest kthLargest = new KthLargest(3, arr);
6
kthLargest.add(3); // returns 4
7
kthLargest.add(5); // returns 5
8
kthLargest.add(10); // returns 5
9
kthLargest.add(9); // returns 8
10
kthLargest.add(4); // returns 8
11
Note:
12
You may assume that nums' length ≥ k-1 and k ≥ 1.
Copied!
使用最小堆完成,不过需要注意length< k的情况。这里补INT_MIN
1
class KthLargest {
2
priority_queue<int,vector<int>,greater<int>>kth;
3
public:
4
KthLargest(int k, vector<int>& nums) {
5
6
7
for(auto n:nums)
8
kth.push(n);
9
for(int i=nums.size();i<k;i++)
10
kth.push(INT_MIN);
11
for(int i=0;i<int(nums.size())-k;i++)
12
kth.pop();
13
14
}
15
16
int add(int val) {
17
if(val>kth.top())
18
{
19
kth.pop();
20
kth.push(val);
21
}
22
23
return kth.top();
24
}
25
};
26
27
/**
28
* Your KthLargest object will be instantiated and called as such:
29
* KthLargest* obj = new KthLargest(k, nums);
30
* int param_1 = obj->add(val);
31
*/
32
Copied!
执行用时 :64 ms, 在所有 C++ 提交中击败了89.78%的用户 内存消耗 :19.3 MB, 在所有 C++ 提交中击败了87.57%的用户
Copy link