295. Find Median from Data Stream

這題最無腦就是每次find時先sort, 但時間複雜度為O(n logn)

看完討論後, 用min, max heap幫助我們

我們會維護一組min heap , max heap

max heap裝的是中位數以下的數字

min heap裝的是中位數之上的

當有數字加入, 我們比較一下, 假設他在比min heap的最大值還要大, 那就加到high那邊去

反之就加在自己low這組

加完後, 很可能兩邊不平衡, 我們平衡一下, 如果 high 比low還要多, high就挑出自己最小的放到low, 當low的數字比high要多出兩個(多出一個沒關係), 那low也要把他的最大值給讓出

插入的時間複雜度為O(logn)

取出時, 我們判斷兩個heap的總數是否為奇數

是的話就拿low那邊的最大值就行了

不是的話low取出最大值, high取出最小值, 相加除2

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
}
void addNum(int num) {
        if (low.empty() || num <= low.top()) {
            low.push(num);
        } else {
            high.push(num);
        }
// Balance
        if (low.size() < high.size()) {
            low.push(high.top());
            high.pop();
        } else if (low.size() - high.size() >= 2) {
            // low greater than high 2 element, (one is accept)
            high.push(low.top());
            low.pop();
        }
    }
double findMedian() {
        if((low.size() + high.size()) % 2 == 1){
            return low.top();
        }else{
            return (low.top() + high.top()) / 2.0;
        }
    }
private:
    priority_queue<int> low;                            // max heap
    priority_queue<int, vector<int>, greater<int>> high; // min heap
};