题解 | #数据流中的中位数#

解法一：插入排序

public:
    //插入排序
    vector<int>ans;
    void Insert(int num) {
        if(ans.empty()){//如果为空，直接插入
            ans.push_back(num);
        }
        else{
            vector<int>::iterator it=lower_bound(ans.begin(),ans.end(),num);//找到大于等于这个数的第一个位置
            ans.insert(it,num);//然后再这个数前面插入
        }
    }

    double GetMedian() { 
        int size=ans.size();
        if(size&1){//奇数个数
            return ans[size/2];
        }else{//偶数个数
            return (ans[size/2-1]+ans[size/2])/2.0;
        }
    }

};