此网站服务器不在国内维护,手机排行榜,杭州pc手机网站建设,万网做网站个人主页#xff1a;C忠实粉丝 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 C忠实粉丝 原创 优先级队列(2)_数据流中第k大元素 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记#xff0c;欢迎大家在评论区交流讨论#x1f48c; 目… 个人主页C忠实粉丝 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 C忠实粉丝 原创 优先级队列(2)_数据流中第k大元素 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记欢迎大家在评论区交流讨论 目录 1. 题目链接
2. 题目描述
3. 解法
算法思路:
代码展示: 1. 题目链接
OJ链接 : 数据流中第k大元素https://leetcode.cn/problems/kth-largest-element-in-a-stream/description/
2. 题目描述
设计一个找到数据流中第 k 大元素的类class。注意是排序后的第 k 大元素不是第 k 个不同的元素。
请实现 KthLargest 类
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。int add(int val) 将 val 插入数据流 nums 后返回当前数据流中第 k 大的元素。 示例 1
输入 [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); // 返回 4 kthLargest.add(5); // 返回 5 kthLargest.add(10); // 返回 5 kthLargest.add(9); // 返回 8 kthLargest.add(4); // 返回 8 示例 2
输入 [KthLargest, add, add, add, add] [[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]
输出[null, 7, 7, 7, 8]
解释
KthLargest kthLargest new KthLargest(4, [7, 7, 7, 7, 8, 3]); kthLargest.add(2); // 返回 7 kthLargest.add(10); // 返回 7 kthLargest.add(9); // 返回 7 kthLargest.add(9); // 返回 8 提示
0 nums.length 1041 k nums.length 1-104 nums[i] 104-104 val 104最多调用 add 方法 104 次 3. 解法
算法思路:
这道题是经典的top-k问题, 使用堆来解决: 1. 创建一个大小为k的堆 (大根堆 or 小根堆)
2, 循环: a. 依次jindui b. 判断堆的大小是否超过k
使用大根堆还是小根堆?
这里很明显需要使用小根堆, 因为我们需要取第k大的元素, 在小根堆中就是堆顶元素
代码展示:
class KthLargest {priority_queueint, vectorint, greaterint heap;int _k;
public:KthLargest(int k, vectorint nums) {_k k;for(auto num : nums){heap.push(num);if(heap.size() _k) heap.pop();} }int add(int val) {heap.push(val);if(heap.size() _k) heap.pop();return heap.top(); }
};/*** Your KthLargest object will be instantiated and called as such:* KthLargest* obj new KthLargest(k, nums);* int param_1 obj-add(val);*/ 知识补充: 我们建的堆默认是大顶堆 greaterint: 这是 C 标准库中的一个函数对象或称为仿函数它会对两个元素进行比较。如果第一个元素小于第二个元素它返回 true否则返回 false。换句话说它表示一种“升序”的排序。
