數據結構問題集錦 - Find Median from Data Stream

臨近期末，鴨梨山大啊，就不多說了。這道題的要求就是，給定一串輸入，在中間任何一個時候，都能夠求出添加到一半的序列的中位數。

大概考慮一下，如果用動態數組來進行元素插入的話，盡管這樣查詢中位數的復雜度為O(1)，由于每一次插入都是O(n)，因而總復雜度為O(n^2)，顯然遭不住。如果用鏈表的話，插入單次還是O(n)，而且求中位數反而更不是O(1)了，也不行。這時候注意到我們需要一個有序的序列來求中位數，所以可以建兩個set，分別存放左半和右半序列，由于set本身數據是有序的，這樣很容易就能查找到中位數了。

于是就可以寫出如下代碼：

template <typename T>
T last(set<T> _set)
{
    return *(_set.rbegin());
}

template <typename T>
T first(set<T> _set)
{
    return *(_set.begin());
}

class MedianFinder {
private:
    set<int> left, right;
public:
    //Adds a number into the data structure.
    void addNum(int num) {
        //Add new number first
        if (left.empty()||(num<=last(left)))
            left.insert(num);
        else
            right.insert(num);
        
        //Arrange left and right queue
        if (left.size()>=right.size()+2)
        {
            right.insert(last(left));
            left.erase(last(left));
        }
        else if (left.size()<right.size())
        {
            left.insert(first(right));
            right.erase(first(right));
        }
    }

    //Returns the median of current data stream
    double findMedian() {
        if (left.size()==right.size())
            return (last(left)+first(right))/2;
        else
            return last(left);
    }
};

大家都知道C++中set是用紅黑樹實現的，于是每一次addNum都應該是O(log n)復雜度，findMedian函數寫的其實不夠好，因為每次添加過后其實都可以記錄下當前的中位數，避免到set中去查找最后一項（現在復雜度是O(log n)，如此重新設計之后能變成O(1)）

不過悲催的是Leetcode還是Time Limit Exceeded了，果然我是算法渣啊...

?