703. 数据流中的第K大元素

用小根堆来保存k大的元素,堆顶即为第k大的元素。

class KthLargest {
priority_queue<int, vector<int>, greater<int> > pq;
int n;
public:
    KthLargest(int k, vector<int>& nums) {
        n = k;
        for(auto it: nums){
            add(it);
        }
    }
    
    int add(int val) {
        if(pq.size() < n) pq.push(val);
        else if(pq.top() < val){
            pq.pop();
            pq.push(val);
        }
        return pq.top();
    }
};

优先队列
常用函数 push() pop() top() size() empty()
优先队列的本质是堆

#include<bits/stdc++.h>
using namespace std;
int main(){
	priority_queue<int> q;  //默认大根堆 
	priority_queue<int, vector<int>, greater<int> > p; //小根堆 
	p.push(3); 
	p.push(6);
	p.push(35);
	q.push(3); 
	q.push(6);
	q.push(35);
	cout<<q.top()<<endl; //35
	cout<<p.top()<<endl; //3
	return 0;
} 
全部评论

相关推荐

07-22 11:12
门头沟学院 Java
不是,我就随手投的怎么还真发面试啊
皮格吉:大厂特别快的——来自已经被共享中
点赞 评论 收藏
分享
点赞 评论 收藏
分享
Vincent777...:实习经历可以考虑放上去,对于软件使用方面可以细化一些,比如调整为:熟悉基于LSDYNA的瞬态动力学仿真分析,熟悉基于WORKBENCH的结构拓扑优化
我的简历长这样
点赞 评论 收藏
分享
06-10 23:36
已编辑
首都经济贸易大学 C++
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务