题目描述

blablabla

样例

blablabla

算法1

class Solution {
public:
    priority_queue<int> small;
    priority_queue<int, vector<int>, greater<int> > large;
    void insert(int num){
        if (small.empty() || num<small.top()) {
            small.push(num);
        }
        else large.push(num);

        if (large.size()==small.size()+1) {
            small.push(large.top());
            large.pop();
        }
        if (small.size()==large.size()+2) {
            large.push(small.top());
            small.pop();
        }

    }

    double getMedian(){
        if (small.size()==large.size()) {
            return (small.top()+large.top())/2.0;
        }
        else return small.top();
    }
};