leetcode295. Find Median From Data Stream

问题描述：

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example,

[2,3,4] , the median is 3 

[2,3], the median is (2 + 3) / 2 = 2.5 

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

解题思路：

这道题要求我们给出输入的数字流的中位数。

若我们有vector来进行存储，那么时间复杂度就会相对较高。

因为中位数是将一个集合分成了大小相差不大于1的两个集合，我们可以用堆来对字符流进行分类。

中位数左边的为最大堆：用less

中位数右边的为最小堆：用greater

每加入一个新的数字x是，判断其与当前中位数m的关系:

　　1. x >= m, 加入右边集合 

　　2. x < m, 加入左边集合

需要注意的是，加入后需要判断当前两集合是否平衡：根据大小来判断。

取值的时候， 根据两边堆的大小（即整体集合为偶数还是奇数）来判断当前应该取一个值还是平均值。

代码：

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        if(rightHeap.empty()){
            rightHeap.push(num);
        }else{
            int mid = rightHeap.top();
            if(num >= mid){
                rightHeap.push(num);
            }else{
                leftHeap.push(num);
            }
        }
        int diff = rightHeap.size() - leftHeap.size();
        if(diff > 0 && diff > 1){
            int temp = rightHeap.top();
            rightHeap.pop();
            leftHeap.push(temp);
        }else if(diff < 0 ){
            int temp = leftHeap.top();
            leftHeap.pop();
            rightHeap.push(temp);
        }
    }
    
    double findMedian() {
        if(rightHeap.size() == leftHeap.size()){
            int r = rightHeap.top();
            int l = leftHeap.top();
            return (double)(r + l) / 2.0;
        }
        return (double)rightHeap.top();
    }
private:
    priority_queue<int, vector<int>, less<int>> leftHeap;
    priority_queue<int, vector<int>, greater<int>> rightHeap;
};

另一种解法：

http://www.cnblogs.com/grandyang/p/4896673.html