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

一.题意整理

由题意可知本题要求对于每个输入的数据求出当前录入的数据的中位数。

二.思路整理

由于要求求出每一次输入数据的中位数，要知道求中位数首先想到就是排序，将每次数据进行排序，然后根据每一次数据个数求出中位数。当然这个思路是肯定可以的，但是时间复杂度偏高，每次利用sort排序的时间复杂度就已经达到了$O(logn)O(logn)$，进一步我们可以利用堆这种数据结构来实现。我们想到中位数之和排序后数据中中间的一个或者两个数据有关，所以我们可以利用两个堆栈，分别去维护左边的最大值和最小值，进而求出中位数，同时也大大降低了时间复杂度。

建立两个堆左边是大根堆，右边是小根堆 分别返回左边的最大值和右边的最小值
1.当我们已经添加的数据个数为奇数个时，将左堆中的最大数放入右边堆中，右堆顶出堆。
2.当我们已经添加的数据个数为偶数个时，将右堆中的最大数放入左边堆中，左堆顶出堆。

三.代码实现

class Solution {
public:
    priority_queue<int>l;//左边的大根堆 返回左边的最大值
    priority_queue<int,vector<int>,greater<int>>r;//右边的小根堆，返回右边的最大值
    int cnt=0;//记录两个堆中元素个数
    void Insert(int num) {
       if(cnt%2==1) {
            l.push(num);
            r.push(l.top()); 
            l.pop();
        } else {
            r.push(num);
            l.push(r.top()); 
            r.pop();
        }
        cnt++;
    }

    double GetMedian() { 
        //根据奇偶计算中位数
         if(cnt%2==1) return l.top();
         else return (l.top()+r.top())/2.0;
     }

};