题目

find-median-from-data-stream

2. 算法

* priority_queue

* multiset

3. 代码

* priority_queue

class MedianFinder {
public:

    // Adds a number into the data structure.
    void addNum(int num) {
        small.push(num);
        large.push(-small.top());
        small.pop();
        if (small.size() < large.size()) {
            small.push(-large.top());
            large.pop();
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        return small.size() > large.size() ? small.top() : 0.5 *(small.top() - large.top());
    }

private:
    priority_queue<long> small, large;
};

* multiset

class MedianFinder {
public:

    // Adds a number into the data structure.
    void addNum(int num) {
        small.insert(num);
        large.insert(-*small.begin());
        small.erase(small.begin());
        if (small.size() < large.size()) {
            small.insert(-*large.begin());
            large.erase(large.begin());
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        return small.size() > large.size() ? *small.begin() : 0.5 * (*small.begin() - *large.begin());
    }

private:
    multiset<long> small, large;
};