中位数是排序后列表的中间值。如果列表的大小是偶数，则没有中间值，此时中位数是中间两个数的平均值。
示例:
[2,3,4] , 中位数是 3
[2,3], 中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中增加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
例如：
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
详见：https://leetcode.com/problems/find-median-from-data-stream/description/
方法一：
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
maxH={};
minH={};
}
void addNum(int num) {
if(((minH.size() + maxH.size()) & 0x1) == 0)
{
if(!maxH.empty() && num<maxH[0])
{
maxH.push_back(num);
push_heap(maxH.begin(),maxH.end(),less<int>());
num = maxH[0];
pop_heap(maxH.begin(),maxH.end(),less<int>());
maxH.pop_back();
}
minH.push_back(num);
push_heap(minH.begin(),minH.end(),greater<int>());
}
else
{
if(!minH.empty() && num>minH[0])
{
minH.push_back(num);
push_heap(minH.begin(),minH.end(),greater<int>());
num = minH[0];
pop_heap(minH.begin(),minH.end(),greater<int>());
minH.pop_back();
}
maxH.push_back(num);
push_heap(maxH.begin(),maxH.end(),less<int>());
}
}
double findMedian() {
int size = minH.size() + maxH.size();
double median = 0;
if((size&0x1) == 1)
{
median = minH[0];
}
else
{
median = (minH[0]+maxH[0])*0.5;
}
return median;
}
private:
vector<int> maxH;
vector<int> minH;
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
方法二：
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
small.push(num);
large.push(-small.top());
small.pop();
if(small.size()<large.size())
{
small.push(-large.top());
large.pop();
}
}
double findMedian() {
return small.size()>large.size()?small.top():0.5*(small.top()-large.top());
}
private:
priority_queue<int> small,large;
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
方法三：
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
small.insert(num);
large.insert(-*small.begin());
small.erase(small.begin());
if(small.size()<large.size())
{
small.insert(-*large.begin());
large.erase(large.begin());
}
}
double findMedian() {
return small.size()>large.size()?*small.begin():0.5*(*small.begin()-*large.begin());
}
private:
multiset<int> small,large;
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
方法四：
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
if(maxH.empty()||num<=maxH.top())
{
maxH.push(num);
}
else
{
minH.push(num);
}
if(minH.size()+2==maxH.size())
{
minH.push(maxH.top());
maxH.pop();
}
if(maxH.size()+1==minH.size())
{
maxH.push(minH.top());
minH.pop();
}
}
double findMedian() {
return minH.size()==maxH.size()?0.5*(minH.top()+maxH.top()):maxH.top();
}
private:
priority_queue<int,vector<int>,less<int>> maxH;
priority_queue<int,vector<int>,greater<int>> minH;
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
参考：https://blog.csdn.net/sjt19910311/article/details/50883735
https://www.cnblogs.com/grandyang/p/4896673.html
295 Find Median from Data Stream 数据流的中位数
原文：https://www.cnblogs.com/xidian2014/p/8776419.html