设计一个找到数据流中第 k 大元素的类(class)。注意是排序后的第 k 大元素,不是第 k 个不同的元素。
请实现 KthLargest 类:
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。 int add(int val) 将 val 插入数据流 nums 后,返回当前数据流中第 k 大的元素。
示例:
输入: ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] 输出: [null, 4, 5, 5, 8, 8]
解释: 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
提示: 1 <= k <= 104 0 <= nums.length <= 104 -104 <= nums[i] <= 104 -104 <= val <= 104 最多调用 add 方法 104 次 题目数据保证,在查找第 k 大元素时,数组中至少有 k 个元素
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/kth-largest-element-in-a-stream 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
用数组把所有元素存起来然后每add一次sort排序。然后就会超时
利用heap的小根堆,但还是会超时
class KthLargest {
public:
vector<int> num;
int k;
KthLargest(int k, vector<int>& nums) {
this->k = k;
for (auto& x: nums) {
add(x);
}
}
int add(int val) {
num.push_back(val);
make_heap(num.begin(), num.end(), greater<int>());
if (num.size() > k) {
pop_heap(num.begin(), num.end(), greater<int>());
num.pop_back();
}
return num[0];
}
};
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest* obj = new KthLargest(k, nums);
* int param_1 = obj->add(val);
*/
来自官方题解的优先队列: 我们可以使用一个大小为 kk 的优先队列来存储前 kk 大的元素,其中优先队列的队头为队列中最小的元素,也就是第 kk 大的元素。
在单次插入的操作中,我们首先将元素 textit{val}val 加入到优先队列中。如果此时优先队列的大小大于 kk,我们需要将优先队列的队头元素弹出,以保证优先队列的大小为 kk
作者:LeetCode-Solution 链接:https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/solution/shu-ju-liu-zhong-de-di-k-da-yuan-su-by-l-woz8/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
class KthLargest {
public:
priority_queue<int, vector<int>, greater<int>> q;
int k;
KthLargest(int k, vector<int>& nums) {
this->k = k;
for (auto& x: nums) {
add(x);
}
}
int add(int val) {
q.push(val);
if (q.size() > k) {
q.pop();
}
return q.top();
}
};
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest* obj = new KthLargest(k, nums);
* int param_1 = obj->add(val);
*/