Find Median from Data Stream

题目来源
设计一个数据结构找中位数。
我一开始想的是用一个vector，然后addNum的时候，二分，找到合适的位置，插入，维持一个有序的状态，可以AC，但是比较麻烦，代码也比较长。
代码如下：

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        int n = nums.size();
        if (n == 0) {
            nums.push_back(num);
            return;
        }
        int l = 0, r = n - 1;
        int mid;
        while (l <= r) {
            mid = (l + r) / 2;
            if (nums[mid] == num) {
                nums.insert(nums.begin()+mid+1, num);
                return;
            }
            else if (nums[mid] > num)
                r = mid - 1;
            else
                l = mid + 1;
        }
        if (nums[mid] > num)
            nums.insert(nums.begin()+mid, num);
        else
            nums.insert(nums.begin()+mid+1, num);
    }
    
    double findMedian() {
        int n = nums.size();
        int mid = (n - 1) / 2;
        if (n % 2 != 0)
            return nums[mid];
        else
            return (nums[mid] + nums[mid+1]) / 2.0;
    }
    
private:
    vector<int> nums;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

看了下讨论区，可以直接用优先队列来做，代码如下：

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        small.push(num);//注意这里每个元素需要先入small再入large，否则可能导致大的在small，如1，2，3
        large.push(-small.top());
        small.pop();
        if (large.size() > small.size()) {
            small.push(-large.top());
            large.pop();
        }
    }
    
    double findMedian() {
        if ((small.size() + large.size()) % 2 == 0)
            return (small.top() - large.top()) / 2.0;
        else
            return small.top();
    }
    
private:
    priority_queue<int> small, large;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */