题目描述

描述：随机产生数字并传递给一个方法。你能否完成这个方法，在每次产生新值时，寻找当前所有值的中间值（中位数）并保存。

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[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

解题思路

思路：最直观的想法是，一个大根堆一个小根堆。中值指的是一个有序数组的最中间的一个数或者中间两个数的平均值，那么可以选择排序，但是排序所需要的时间复杂度太高了，所以就考虑什么方法能取到最中间的两个数呢？想象把数组分为两半部分，左半部分我们需要取到最右边的数，即可以使用一个大根堆存储，右半部分我们需要取到最左边的数，即可以使用一个小根堆存储。考虑到数组长度可能为奇数可能为偶数，所以我们默认设计当数组长度为奇数时小根堆比大根堆多存储一个数。

//默认是大根堆 大根堆是less<int>
priority_queue<int> maxpq;
//注意 小根堆是greater<int>
priority_queue<int,vector<int>,greater<int>> minpq;
MedianFinder() {
}
//假设小根堆可以比大根堆多一个
void addNum(int num) 
{if(minpq.empty()||num>=minpq.top()){if(maxpq.size()<minpq.size()){maxpq.push(minpq.top());minpq.pop();}//当两者相等时直接插入小根堆minpq.push(num);}//num<minpq.top()但是可能num>maxpq.top()else{//所以需要先插入再比较maxpq.push(num);if(maxpq.size()>minpq.size())  {minpq.push(maxpq.top());maxpq.pop();               }     }
} 
double findMedian() 
{return maxpq.size()==minpq.size()?(maxpq.top()+minpq.top())/2.0 :minpq.top();
}

总结：注意此处，是先插入再比较，还是先比较再插入。注意语法，less<int>是大根堆，而greater<int>是小根堆。