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.

Examples:
[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.
For example:

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

解題思路

使用兩個priority_queue來模擬兩個堆，其中的一個大根堆minH用來存儲較大的那一半元素，另一個小根堆maxH用來存儲較小的那一半元素。則，中位數要麼是其中一個堆（元素較多的堆）的top元素，要麼是兩個堆的top元素的均值。

實現代碼

C++:

// Runtime: 212 ms
class MedianFinder {
public:
    // Adds a number into the data structure.
    void addNum(int num) {
       minH.push(num);
       int n = minH.top();
       minH.pop();
       maxH.push(n);
       int len1 = maxH.size();
       int len2 = minH.size();
       if (len1 > len2)
       {
           n = maxH.top();
           maxH.pop();
           minH.push(n);
       }
    }

    // Returns the median of current data stream
    double findMedian() {
        int len1 = maxH.size();
        int len2 = minH.size();
        if (len1 == len2)
        {
            return (maxH.top() + minH.top()) / 2.0;
        }
        else
        {
            return len1 > len2 ? maxH.top() : minH.top();
        }
    }

private:
    priority_queue, less> maxH;
    priority_queue, greater> minH;
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();

Java:

// Runtime: 50 ms
class MedianFinder {
    private Queue maxH = new PriorityQueue(Collections.reverseOrder());
    private Queue minH = new PriorityQueue();
    // Adds a number into the data structure.
    public void addNum(int num) {
        minH.offer(num);
        int n = minH.poll();
        maxH.offer(n);
        int len1 = maxH.size();
        int len2 = minH.size();
        if (len1 > len2) {
            n = maxH.poll();
            minH.offer(n);
        }
    }

    // Returns the median of current data stream
    public double findMedian() {
        int len1 = maxH.size();
        int len2 = minH.size();
        if (len1 == len2) {
            return (maxH.peek() + minH.peek()) / 2.0;
        }
        else {
            return len1 > len2 ? maxH.peek() : minH.peek();
        }
    }
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();