295. 數據流的中位數

思路

有一連串的資料持續輸入，輸入中途會要求輸出當前的中位數。
創建兩個堆，一個最大堆，一個最小堆，先不去考慮會不斷有數字進來。
假設現在已經有全部的數字，把排序好的，比較小的一半放在最大堆，比較大的一半放在最小堆，如果一共有奇數個，將 $n/2+1$ 個數字放到最大堆。
此時兩個堆取top，假如有奇數個，答案就是最大堆的top，假如有偶數個，就是兩個top相加除以二。

這時再去考慮不斷有數字進入的情況。
每當數字進來，就去調整最大堆跟最小堆的數量，讓兩者的大小差在 1（包含）以下，
如果最大堆放太多數字，就將它的top（左半部分最大的數字），移動到最小堆（移動到右半邊）。
反之就將最小堆的top移動到最大堆。找中位數的方法如上面所說。

程式碼

優先隊列

class MedianFinder {
private:
    priority_queue<int> maxHeap; // 左半部分
    priority_queue<int, vector<int>, greater<int>> minHeap; // 右半部分
public:
    MedianFinder() {}
    
    void addNum(int num) {
        if(maxHeap.empty() || maxHeap.top() > num) {
            maxHeap.push(num);
        }
        else {
            minHeap.push(num);
        }
        if(maxHeap.size() - minHeap.size() == 2 || maxHeap.size() - minHeap.size() == -2) {
            if(maxHeap.size() > minHeap.size()) {
                minHeap.push(maxHeap.top());
                maxHeap.pop();
            }
            else {
                maxHeap.push(minHeap.top());
                minHeap.pop();
            }
        }
    }
    double findMedian() {
        if(maxHeap.size() == minHeap.size()) {
            return (double)(maxHeap.top() + minHeap.top()) / 2;
        }
        else {
            return maxHeap.size() > minHeap.size() ? (double)maxHeap.top() : (double)minHeap.top();
        }
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(n)$