题解 | #数据流中的中位数# 插入排序法

#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);

            v.insert(it, num); // 在不小于此元素的位置 插入
        }
        
    }

    double GetMedian() { 
        int n = v.size();
        if(n&1)
        {
            // 奇数
            return double(v[n>>1]);
        }
        else
        {
            return double((v[n>>1]+v[(n>>1) - 1])/2.);
        }
    
    }

};

但 进行插入排序的时间复杂度反而大了