class Solution {
public:
priority_queue<int> max_heap;
priority_queue<int,vector<int>,greater<int>> min_heap;
void insert(int num){
max_heap.push(num);//先插入大根堆
if(min_heap.size()&&max_heap.top()>min_heap.top())//如果逆序了,交换一下
{
int maxv=max_heap.top(),minv=min_heap.top();
max_heap.pop();min_heap.pop();
max_heap.push(minv);min_heap.push(maxv);
}
while(max_heap.size()>min_heap.size()+1)//保证两堆数目平均
{
int val=max_heap.top();
max_heap.pop();
min_heap.push(val);
}
}
double getMedian(){
if(max_heap.size()+min_heap.size()&1) return max_heap.top();
else return (max_heap.top()+min_heap.top())/2.0;
}
};
数据流中的中位数
发布时间 2023-04-19 16:18:39作者: 穿过雾的阴霾