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

思路：利用 C++ 的有序容器 set 进行数据存储，并使用一个指针，一直指向中位数的位置。
时间复杂度 ，GetMedian 是 O（1），Insert 是 O（log（n）），因为 set 的插入效率是 O（log（n））。
这个方法，比大根堆好理解些，代码量不大。

题解：
1.因为元素可能出现重复，所以使用 set 的可重复元素的版本，multiset

2.使用 multiset::iterator mid 作为中位数存储指针，需要在 Insert 时候，对其进行维护

3.奇数时， mid 指向中位数， 偶数时， mid 指向 中间两数的左边那个。

4.插入时，如果数据长度原本为奇数，插入后则为偶数。如果插入的数据比原中位数要小，则中位数指针左移一位。（这个可以自己画图理解）

5.如果数据长度原本为偶数，插入后则为奇数。如果插入的数据比原中位数要大，则中位数指针右移一位。（可以自己画图理解）

class Solution {
    public:
    void Insert(int num) 
    {
        data.insert(num);

        //维护中位数指针
        if (data.size() == 1)  //初始化
            mid = data.begin();
        else if (data.size() %2 == 0) //偶数
        {
            if (num < *mid)
                mid -- ;
        }
        else //奇数
        {
            if (num >= *mid)
                mid ++ ;
        }
    }

    double GetMedian() 
    { 
        if (data.size() %2 == 0) //偶数
        {
            auto mid2 = mid; 
            mid2++; // 中间第二个数
            return ((double)*mid + *(mid2)) / 2; //均值
        }
        else //奇数
        {
            return *mid;
        }    
    }

    private:
    
    multiset<int> data;
    multiset<int>::iterator mid;
};