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; }
};