AcWing 54. 数据流中的中位数
原题链接
困难
作者:
UKN
,
2023-01-11 20:30:17
,
所有人可见
,
阅读 76
双堆
C++ 代码
class Solution {
public:
priority_queue<int> q1;//大根堆
priority_queue<int,vector<int>, greater<int>> q2;//小根堆
void insert(int num){
if(q1.empty())q1.push(num);
else if(num >= q1.top())q2.push(num);
else q1.push(num);
}
double getMedian(){
int n = q1.size(), m = q2.size();
int dg = (n+m)%2;
if(dg)
{
while(n != m+1)
{
if(n && n > m + 1){
int t = q1.top();
q1.pop();
q2.push(t);
}
if(m && n < m + 1){
int t = q2.top();
q2.pop();
q1.push(t);
}
n = q1.size(), m = q2.size();
}
return q1.top();
}
else
{
while(n != m)
{
if(n && n > m){
int t = q1.top();
q1.pop();
q2.push(t);
}
if(m && n < m){
int t = q2.top();
q2.pop();
q1.push(t);
}
n = q1.size(), m = q2.size();
}
return (q1.top()+q2.top())/2.0;
}
}
};