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

使用插入排序保证每次插入后序列都是有序的。同时注意insert方法是在指定迭代器前方插入（而不是在当前迭代器位置插入）！！！

class Solution {
  public:
    //  使用插入排序，每次插入之后都直接是有序序列
    void Insert(int num) {
      if (steam.empty()) {
        steam.push_back(num);
        return ;
      }
      
      int idx = steam.size() - 1;
      
      for (; idx >= 0 && steam[idx] > num; --idx) {
      }
      
      auto it = steam.begin() + idx + 1;
      
      steam.insert(it, num);
    }

    //  本身已经有序
    double GetMedian() { 
      int half_size = steam.size() / 2;
      
      //  奇数个
      if (steam.size() % 2) {
        return static_cast<double>(steam[half_size]);
      } else {
        return static_cast<double>(steam[half_size] + steam[half_size - 1]) / 2;
      }
    }

  private:
    std::vector<int> steam;
};