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

方法1：暴力
我们使用一个vector来存数组
并且对于每次中位数的计算，我们直接排序一遍，然后寻找中位数即可
时间复杂度：插入数字O(1)，查找中位数O(nlogn)
空间复杂度：O(n)

class Solution {
public:
    vector<int> v;//用于存数组
    void Insert(int num) {
        v.push_back(num);
    }
    double GetMedian() { 
        sort(v.begin(), v.end());
        int sz = v.size();
        if (sz & 1) return v[sz / 2];//如果是奇数个，则是中间的那个
        else return (v[sz / 2] + v[sz / 2 - 1]) / 2.0;//否则就是中间的两个取平均值
    }
};

方法2：对顶堆
这个是利用了STL中的priority_queue可以取最值的特性来做动态取中位数的题目
我们创建两个堆，一个用大顶堆，一个用小顶堆
我们要保证
序列中前个元素在大根堆中，剩余的都在小根堆中
当一共有奇数个元素时，中位数是小根堆顶
当一共有偶数个元素时，中位数是大根堆顶
过程是这样的
第一个元素放到小根堆中
接下来插入的元素，当该元素大于当前中位数，就插入到小根堆顶，否则插入到大根堆顶
如果大根堆的元素个数大于小根堆的元素个数，就让大根堆顶弹出到小根堆中
如果小根堆的元素个数-大根堆的元素个数 > 1，就让小根堆顶弹出到大根堆中
接下来给大家模拟一下
我们依次将[5、2、3、4、1、6、7]插入序列中
首先是第一个元素，我们插入小根堆

然后是第二个元素，我们发现比当前中位数少，于是插入到大根堆中
因为是偶数个元素，于是中位数大根堆堆顶和小根堆堆顶的平均数

第三个元素，我们发现比当前中位数少，于是插入到大根堆中
此时，大根堆元素比小根堆多，于是将大根堆堆顶弹出到小根堆中

第四个元素，我们发现比当前中位数大，于是插入到小根堆中
此时，小根堆元素比大根堆多，于是将小根堆堆顶弹出到大根堆中

接下来依次类推



时间复杂度：插入数字O(logn)，求中位数O(logn)
空间复杂度：O(n)

class Solution {
public:
    priority_queue<int> q1;//大根堆
    priority_queue<int, vector<int>, greater<>> q2;//小根堆
    double now;//当前中位数
    int cnt = 0;//当前插入的元素个数
    void Insert(int num) {
        cnt ++ ;
        if (q2.empty()) q2.push(num);//插入第一个元素
        else {
            //选择插入的堆
            if (num < now) q1.push(num);
            else q2.push(num);
        }
        //插入之后调整堆
        if (q1.size() > q2.size()) {
            q2.push(q1.top());
            q1.pop();
        } else if (q2.size() - q1.size() > 1) {
            q1.push(q2.top());
            q2.pop();
        }
    }
    double GetMedian() { 
        //记得更新now
        if (cnt & 1) now = q2.top();
        else now = (q2.top() + q1.top()) / 2.0;
        return now;
    }
};