题目
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。例如：
[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
思路
所谓求有序列表的中位数，就是返回该有序列表中第中位数个最大值，又是对于堆（优先队列）的应用。所以，可以先将所有值压入堆中，如果是奇数，弹出floor(data.size/2)个元素后，访问并输出堆顶即可；如果是偶数，弹出floor(data.size/2)-1个元素后，取出堆顶两个元素求平均即可。
但对于本题，因为有序列表长度是动态递增的，而不是静态固定的长度，所以如果按上面提到的思路解决，需要先弹出，然后访问，接着又压入，这样大大提高了算法的时间复杂度和空间复杂度。因此需要寻求其他方法。
因为是有序列表，因此中位数前面的元素一定比中位数小，而后面的元素一定比中位数大。根据这个性质可以将有序列表分为两部分，然后使用最大堆去存储中位数前面的元素，使用最小堆去存储中位数后面的元素。最后根据有序列表长度是偶数还是奇数，返回两个堆堆顶的平均值或最大堆的堆顶（奇数个时，用最大堆存储多出来的数）。算法如下：
- 将新添加的数压入最大堆；
- 将最大堆堆顶元素弹出并压入在最小堆中；
- 如果最大堆的size小于最小堆的size，则将最小堆堆顶元素弹出并压入最大堆；
-
访问中位数时：
- 如果最大堆size大于最小堆size，说明当前是奇数个，所以访问最大堆堆顶即可；
- 如果相等，则说明是偶数个，所以访问两个堆的堆顶求平均值返回。
解答
class MedianFinder {
public:
//始终保持最大堆里是最小的几个数，最小堆里是最大的几个数
void addNum(int num) {
//将最大堆的堆顶压入最小堆
low.push(num);
high.push(low.top());
low.pop();
//需要保持两个堆元素数量平衡，
//如果不平衡，就将最小堆的堆顶压入最大堆
if(low.size() < high.size()) {
low.push(high.top());
high.pop();
}
}
//如果数据流元素数量是奇数，则最大堆的堆顶就是所求中位数
//否则取出两个堆的堆顶求平均
double findMedian() {
if(low.size() > high.size()) //奇数个元素
return (double)low.top();
else //偶数个元素
return (low.top() + high.top()) * 0.5;
}
private:
//最大堆，存放数据流中前半块小的数据
priority_queue<int> low;
//最小堆，存放数据流中后半块大的数据
priority_queue<int, vector<int>, greater<int>> high;
};
【关注公众号DoCode，每日一道LeetCode，将零碎时间利用起来】
