LeetCode 295 Find Median from Data Stream

思路

使用

multiset+pointer

，在向

multiset

插入資料同時更新

pointer

，確定

pointer

總是指向中位數或者第一個中位數如果資料個數是偶數個。

set,multiset,map

的疊代器在插入操作後仍然有效。

代碼

class MedianFinder {
    multiset<int> data;
    multiset<int>::iterator mid;
public:
    MedianFinder() {}
    void addNum(int num) {
        const size_t n = data.size();
        data.insert(num);
        if (n == 0) {
            mid = data.begin();
        } else {
            if (num == *mid)
                mid = n & 1 ? mid : next(mid);
            else if (num < *mid)
                mid = n & 1 ? prev(mid) : mid;
            else
                mid = n & 1 ? mid : next(mid);
        }
    }

    double findMedian() { return data.size() & 1 ? *mid : ((*mid) + (double)(*next(mid))) * 0.5; }
};