IT工程師數位筆記本

如何得到一個數據流中的中位數？如果從數據流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值。如果從數據流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值。

最開始的思路就是用map或者set存儲。習慣寫python就想直接用median的key去訪問median，但是C++ STL的map或者set沒有key這個東西，如果用迭代器那么訪問元素復雜度是O（n）

看到很多解法是用兩個堆來做，一個最大堆，一個最小堆，一開始不理解。后來發現這樣的好處是把數據總體切分為兩部分，一部分（最大堆）所有元素都比另一部分（最小堆）小。然后當有新元素需要insert的時候，根據現有元素總數奇偶，決定先壓入哪個堆，然后彈出一個元素，彈出元素放入另一個堆。

最后的答案處理，根據元素總數奇偶，決定從兩個堆分別取還是從特定的那個取。

class Solution{
public:
    void Insert(int num){
        if (maxS.size() == minS.size()){
            maxS.insert(num);
            minS.insert(*maxS.begin());
            maxS.erase(maxS.begin());
        }
        else{
            minS.insert(num);
            maxS.insert(*minS.begin());
            minS.erase(minS.begin());
        }
    }

    double GetMedian(){
        int num = maxS.size() + minS.size();
        
        double median;
        if ((num&1)==1){
            median = *minS.begin();
        }
        else{
            median = (*maxS.begin() + *minS.begin()) / 2.0;
        }
        return median;
    }
private:
    multiset<int, greater<int> > maxS;
    multiset<int, less<int> > minS;
};