题目

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

[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，将零碎时间利用起来】