中位数是排序后列表的中间值。如果列表的大小是偶数，则没有中间值，此时中位数是中间两个数的平均值。
示例:
[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/
Java实现：
参考：https://www.cnblogs.com/Liok3187/p/4928667.html
O(nlogn)的做法是开两个堆(java用优先队列代替)。
最小堆放小于中位数的一半，最大堆放较大的另一半。
addNum操作，把当前的num放到size小的堆中，通过2次poll-add操作，保证了最小堆中的所有数都小于最大堆中的数。
findMedian操作，如果size不同，就是其中一个堆顶，否则就是连个堆顶的数相加除以2。
class MedianFinder {
private Queue<Integer> maxHeap;
private Queue<Integer> minHeap;
/**
* initialize your data structure here.
*/
public MedianFinder() {
this.maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
this.minHeap = new PriorityQueue<Integer>();
}
public void addNum(int num) {
if (maxHeap.size() < minHeap.size()) {
maxHeap.add(num);
minHeap.add(maxHeap.poll());
maxHeap.add(minHeap.poll());
} else {
minHeap.add(num);
maxHeap.add(minHeap.poll());
minHeap.add(maxHeap.poll());
}
}
public double findMedian() {
if (maxHeap.size() < minHeap.size()) {
return minHeap.peek();
} else if (maxHeap.size() > minHeap.size()) {
return maxHeap.peek();
} else {
return (minHeap.peek() + maxHeap.peek()) / 2.0;
}
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
C++实现：
方法一：
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