分析
优先队列的使用,用其来模拟大根堆和小根堆。
C++ 代码
class Solution {
public:
int co=0;
priority_queue<int> l; //大根堆
priority_queue<int, vector<int>, greater<int> > r; //小根堆
void insert(int num){
if(r.empty() || num>r.top()) r.push(num);
else l.push(num);
co++;
}
double getMedian()
{
if(co%2)
{
while(r.size()>(co+1)/2)
{
l.push(r.top());
r.pop();
}
while(r.size()<(co+1)/2)
{
r.push(l.top());
l.pop();
}
return double(r.top());
}
else{
while(r.size()>co/2)
{
l.push(r.top());
r.pop();
}
while(r.size()<co/2)
{
r.push(l.top());
l.pop();
}
return 1.0*(l.top()+r.top())/2;
}
}
};