题目描述
如何得到一个数据流中的中位数?
如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
样例
输入:1, 2, 3, 4
输出:1,1.5,2,2.5
解释:每当数据流读入一个数据,就进行一次判断并输出当前的中位数。
算法
(大根堆、小根堆)
- 在交换2个堆的元素的时候,一定要 先判断上面的小根堆中有没有元素。 上面的小根堆中 没有元素是不能交换的。
- 小根堆没有元素,就把大根堆中的top放到小根堆中。
时间复杂度
$O(logn)$
C++ 代码
class Solution {
public:
priority_queue<int> maxheap;
priority_queue<int, vector<int>, greater<int> > minheap;
void insert(int x){
maxheap.push(x);
if(minheap.size() && maxheap.top() > minheap.top()) // **1
{
int maxe = maxheap.top(), mine = minheap.top();
maxheap.pop(), minheap.pop();
maxheap.push(mine), minheap.push(maxe);
}
if(maxheap.size() > minheap.size() + 1)
{
minheap.push(maxheap.top());
maxheap.pop();
}
}
double getMedian(){
if((maxheap.size() + minheap.size()) & 1) return maxheap.top();
else return (maxheap.top() + minheap.top()) / 2.0;
}
};