Leetcode 剑指 Offer 41. 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1：

输入：
[“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：

输入：
[“MedianFinder”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

限制：

最多会对 addNum、findMedian 进行 50000 次调用。

方法一：左手一个大顶堆 + 右手一个小顶堆。

解题思路

1. 我们没有必要把所有数据进行排序。只需要保证数据左半边的数都小于右半边的数，那么根据左半边的数的最大值及右半边的数的最小值即可得到中位数。
2. 若输入的数据个数是奇数，比如 1、2、3、4、5。我们可以把左边的 1、2 存入一个大顶堆中，把右边的 3、4、5 存入一个小顶堆中。那么中位数就是小顶堆的 top()。
3. 若输入的数据个数是偶数，比如 1、2、3、4。我们可以把左边的 1、2 存入一个大顶堆中，把右边的 3、4 存入一个小顶堆中。那么中位数就是两个堆的 top() 的和再乘 0.5。
4. 整个过程我们需要维护两个地方：两个堆的 size() 最大只能相差 1；大顶堆的 top() 必须小于等于小顶堆的 top()。

实现方法

5. 每插入一个数之前，先判断两个堆的 size() 是否相等。
6. 若相等，先将这个数插入大顶堆，然后将大顶堆的 top() 插入小顶堆。这么做可以保证小顶堆的所有数永远大于等于大顶堆的 top()。
7. 若不相等，先将这个数插入小顶堆，然后将小顶堆的 top() 插入小顶堆。这么做可以保证大顶堆的所有数永远小于等于小顶堆的 top()。
8. 整个过程我们都动态地做到了平衡两个堆的 size()，即保证它们的 size() 最大只相差了 1。

结果输出

1. 若最后两个堆的 size() 不等。由于当两个堆的 size() 相等时我们总是选择将数插入小顶堆中（先插入大顶堆但马上又将大顶堆的 top() 插入小顶堆），所以中位数一定是小顶堆的 top()。比如数据是 1、2、3、4、5，最后大顶堆中是 1、2，小顶堆中是 3、4、5，中位数是小顶堆的 top()。
2. 若最后两个堆的 size() 相等。那么中位数就是两个堆的 top() 的和再乘 0.5。

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int, vector<int>, less<int> > maxheap;//大顶堆按从大到小排列，队头（pop）元数最大
    priority_queue<int, vector<int>, greater<int> > minheap;//小顶堆按从小到大排列，队头（pop）元数最小

    MedianFinder() {

    }
    
    void addNum(int num) {
        if(maxheap.size() == minheap.size()) {
            maxheap.push(num);
            minheap.push(maxheap.top());
            maxheap.pop();
        }
        else {
            minheap.push(num);
            maxheap.push(minheap.top());
            minheap.pop();
        }
    }
    
    double findMedian() {
        int maxSize = maxheap.size(), minSize = minheap.size();
        if(maxSize==0) return NULL;
        int mid1 = maxheap.top(), mid2 = minheap.top();
        return maxSize == minSize ? ((mid1 + mid2) * 0.5) : mid2;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

int main()
{   
    int num[]={1,2,3};
    double param_2;
    MedianFinder* obj = new MedianFinder();
    param_2 = obj->findMedian();
    cout<<param_2<<endl;
    obj->addNum(num[0]);
    obj->addNum(num[1]);
    param_2 = obj->findMedian();
    cout<<param_2<<endl;
    obj->addNum(num[2]);
    param_2 = obj->findMedian();
    cout<<param_2<<endl;
    system("pause");
    return 0;
}