首页 > 其他 > 详细

堆————数据流的第k个大的元素

时间:2019-06-17 18:07:20      阅读:101      评论:0      收藏:0      [点我收藏+]

技术分享图片

解题思路

一般地,堆和堆排序——解决 "贪心算法及其类似问题" 的利器。

# 思路:我们可以用一个小根堆来做,并且限制堆的大小为k,初始化时把nums的每个数都push到堆中,如果堆的大小大于k,就pop一个元素。对于add方法也是同理。

# 这里使用的数据结构是C++中的“优先队列(priority_queue)",包含在头文件<queue>中。优先队列具有队列的所有特性,包括基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的。

 

 

 1 class KthLargest {
 2 public:
 3     KthLargest(int k, vector<int>& nums) {
 4         l = k;
 5         for(int i=0;i<nums.size();i++){
 6             que.push(nums[i]);
 7             if(que.size() > l) que.pop();
 8         }
 9     }
10     
11     int add(int val) {
12         que.push(val);
13         if(que.size() > l) que.pop();
14         return que.top();
15     }
16 private:
17     priority_queue<int, vector<int>, std::greater<int>> que;//降序,小顶堆,前k个最大的元素
18     int l;    
19 };
20 
21 /**
22  * Your KthLargest object will be instantiated and called as such:
23  * KthLargest* obj = new KthLargest(k, nums);
24  * int param_1 = obj->add(val);
25  */

 

 

 

堆————数据流的第k个大的元素

原文:https://www.cnblogs.com/pacino12134/p/11040624.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!