LeetCode 295. Find Median from Data Stream

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class MedianFinder {
private:
    vector<int> data;
public:
    MedianFinder() {
    }
    void addNum(int num) {
        if (data.empty())
            data.emplace_back(num);
        else
            data.insert(lower_bound(data.begin(), data.end(), num), num);
    }
    double findMedian() {
        int n = data.size();
        return n & 1 ? data[n / 2] : (data[n / 2 - 1] + data[n / 2]) * 0.5;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MedianFinder {
private:
    priority_queue<int> lo; // max heap
    priority_queue<int, vector<int>, greater<int>> hi; // min heap
public:
    MedianFinder() {
    }
    void addNum(int num) {
        lo.push(num);
        hi.push(lo.top());
        lo.pop();
        if (lo.size() < hi.size()) {
            lo.push(hi.top());
            hi.pop();
        }
    }
    double findMedian() {
        return lo.size() > hi.size() ? (double) lo.top() : (lo.top() + hi.top()) * 0.5;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class MedianFinder {
private:
    multiset<int> data;
    multiset<int>::iterator lo, hi;
public:
    MedianFinder(): lo(data.end()), hi(data.end()) {
    }
    void addNum(int num) {
        const int n = data.size();
        data.insert(num);
        if (!n) { // the 1st element.
            lo = hi = data.begin();
        } else if (n & 1) { // odd size before.
            if (num < *lo) --lo;
            else ++hi;
        } else { // even size before.
            if (num > *lo && num < *hi) {
                ++lo;
                --hi;
            } else if (num >= *hi) ++lo;
            else lo = --hi;
        }
    }
    double findMedian() {
        return (*lo + *hi) * 0.5;
    }
};