支线任务－8

Find Median from Data Stream

这个题目看上去说明也是很简单的：设计一个数据结构能够支持两种操作：

加入一个元素
找到当前所有元素的中位数

如果我们将数组能够保持排序的状态那么这个自然好办，就是排序的结果的中间两位，但是排序算法一般都是离线算法，无法动态的修改，唯一能够想到的就是二分查找的插入排序，可是在移动数组下标带来的复杂度远超这个算法能够达到的O(logN)级别，因此排序貌似是不可行的了。

不过既然只要求找到中位数，也就是说在数组中只需要维护一个数字，不禁让我们想起了堆这种数据结构，因为堆也是在动态的维护数组中的一个元素（最大或者最小值），这个题目要求的是中间值，因此我们可以看看怎么借助堆来完成。

既然是中位数，那就代表这个数大于一半数组的数同时小于剩下一半数组的所有数。那么我们就可以通过维护两个一半数组大小的堆来实现：比中位数小的放在一个最大堆里，比中位数大的放在一个最小堆里，中位数就是这两个堆的顶部。

class MedianFinder {
public:

    priority_queue<int, vector<int, allocator<int> >, greater<int> > large;
    priority_queue<int, vector<int, allocator<int> >, less<int> > small;
    int length;
    
    MedianFinder(): length(0){}

    // Adds a number into the data structure.
    void addNum(int num) {
        if (length % 2 == 0)
            if (small.empty() || num <= large.top())
                small.push(num);
            else {
                small.push(large.top());
                large.pop();
                large.push(num);
            }
        else
            if (num >= small.top())
                large.push(num);
            else {
                large.push(small.top());
                small.pop();
                small.push(num);
            }
        ++length;
    }

    // Returns the median of current data stream
    double findMedian() {
        if (length % 2 == 0)
            return (small.top() + large.top()) / 2.;
        else
            return small.top();
    }
};

View Code

代码中描述算法会更清楚，注意一些细节，我的算法是如果大小为奇数就让最大堆大小多一个。复杂度为O(NlogN)