题目描述
如何得到一个数据流中的中位数?
如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
样例
输入:1, 2, 3, 4
输出:1,1.5,2,2.5
算法1
(大小堆) $O(nlogn)$
维护两个堆的平衡,然后注意两个堆绝对大小关系
1. 最大堆的堆顶的数据要比所有的最小堆的数据要小
2. 最小堆的堆顶的数据要比所有的最大堆的数据要大
另外注意最小堆的构建是通过加-号进行
时间复杂度
每个数据流中的数据在插入后,需要常数次数量的堆调整也就是大概o(clog(n/2)) = o(logn)的时间复杂度。
查找时o(1)
总时间复杂度o(nlogn)
C++ 代码
#include <queue>
using namespace std;
class Solution {
public:
priority_queue<int> maxHeap;
priority_queue<int> minHeap;
void insert(int num){
if(!minHeap.empty() && num > -minHeap.top()){
maxHeap.push(-minHeap.top());
minHeap.pop();
minHeap.push(-num);
}else{
maxHeap.push(num);
}
if(maxHeap.size() >= minHeap.size() + 2){
minHeap.push(-maxHeap.top());
maxHeap.pop();
}
}
double getMedian(){
return maxHeap.size() == minHeap.size()? (maxHeap.top()-minHeap.top()) / 2.0 : maxHeap.top();
}
};