题解 | 数据流中的中位数

#include <algorithm>
class Solution {
    /*
        中位数是排好序之后，中间的那个数
    */
public:
    vector<int> v;

    void Insert(int num) {
        if(v.empty()){
            v.push_back(num);
        }else{
            auto it = lower_bound(v.begin(), v.end(), num);   //二分法，找到第一个大于等于的数；up_bound()找到第十个大于的数
            v.insert(it, num);
        }
    }

    double GetMedian() { 
        int sz = v.size();

        if(sz%2 == 1){  //jishu
            return static_cast<double>( v[sz/2] );
        }else{   //even
            return static_cast<double>( ( v[sz/2-1] + v[sz/2] ) )/2;   //整数除2会向下取整，浮点数保留小数
        }
    }

};