题解 | #随时找到数据流的中位数#

题意：

• 设计一个结构，要求可以加入新数，并可以随时返回该结构中所有数据的中位数。

方法一:暴力解法

• 使用一个,是一个有序的元素可重复的数据结构,由平衡二叉树实现的,所以添加元素的时间复杂度为.返回中位数时由于multiset迭代器只能执行++,--的操作,不能直接自增一个量,所以时间复杂度是.
• 增加操作直接即可,寻找中位数通过的长度寻址到最中间一个数或者两个数.

  class Solution {
  public:
    multiset<int> dataStream;
    /**
     * the medians
     * @param operations int整型vector<vector<>> ops
     * @return double浮点型vector
     */
    vector<double> flowmedian(vector<vector<int> >& operations) {
        // write code here
        vector<double> ans;
        for(int i=0;i<operations.size();i++){
            //添加操作
            if(operations[i].size()==2&&operations[i][0]==1)
                add(operations[i][1]);
            //寻找中位数
            else if(operations[i].size()==1&&operations[i][0]==2)
                ans.push_back(findMedian());
        }
        return ans;
    }
    void add(int num){
        //添加,直接insert
        dataStream.insert(num);
    }
    double findMedian(){
        int length=dataStream.size();
        //奇数,寻找下标为length/2的数
        if(length%2){
            auto it=dataStream.begin();
            int x=length/2;
            while(x--){
                it++;
            }
            return *it;
        }else{
             //偶数,寻找下标为length/2与length/2-1的数求平均.
             auto it=dataStream.begin();
             int x=length/2;
             while(x--){
                it++;
             }
             auto it2=it;
             it2--;
             double ans=*it+*it2;
             return ans/2.0;
        }
    }
  };

  复杂度分析：

  时间复杂度：，其中添加，寻找中位数.
  空间复杂度：,额外内存空间。

方法二：

• 思路：本题寻找中位数的要求较为苛刻，即新数加入时间复杂度为O(logn)，返回中位数的时间复杂度为O(1)。看到这两个数字很自然的联想到堆，对于一个最大堆（或者最小堆），把数加入堆的时间复杂度为O(logn)，取出最大值（或者最小值）的时间复杂度为O(1)。但是此处的要求是返回中位数，当数据流中的数量为2n时，返回第n和n+1大的数；当数据流中的数量为2n+1时，返回第n+1大的数。因此可以使用两个堆来组织，即一个存较小值的最大堆low，一个存较大值的最小堆high。

  low:存数据流中较小的一半数，其数量为n，最大堆。
  high:存数据流中较大的一半数，其数量为n或n+1，最小堆。
  其中high中的数都大于low中的数

• 代码逻辑：

  • （1）插入。首先将当前数添加到low中，从low中取出最大值，添加到high中，这是会出现两种情况:A.low中数量为n,high中数量为n+1;B.low中数量为n,high中数量为n+2。情况A已经满足要求，对于情况B，我们需要从high中取出最小值放回low中。堆的插入和删除堆顶元素的时间复杂度都是O(logn)。
  • （2）取出中位数，如果low和high的数量都是n，则取出最大值和最小值求平均即为中位数；否则取出high的最小值作为中位数。由于都是堆，时间复杂度为O(1)。

图解如下：

代码如下：

class Solution {
public:
    priority_queue<int> low;//最大堆，存的是较小一半元素
    priority_queue<int,vector<int>,greater<int>> high;//最小堆，存的是较大一半元素
    /**
     * the medians
     * @param operations int整型vector<vector<>> ops
     * @return double浮点型vector
     */
    vector<double> flowmedian(vector<vector<int> >& operations) {
        // write code here
        vector<double> ans;
        for(int i=0;i<operations.size();i++){
            //添加操作
            if(operations[i].size()==2&&operations[i][0]==1)
                add(operations[i][1]);
            //寻找中位数
            else if(operations[i].size()==1&&operations[i][0]==2)
                ans.push_back(findMedian());
        }
        return ans;
    }
    void add(int num){
        low.push(num);
        int tmp=low.top();
        low.pop();
        high.push(tmp);
        //当high中元素为n+2,low中元素为n->需要从high中移一个元素到low
        if(high.size()>low.size()+1){
            low.push(high.top());
            high.pop();
        }
    }
    double findMedian(){
        //MedianHolder结构为空
        if(high.size()==0)
            return -1;
        //分别为n,n+1
        else if(low.size()<high.size())
            return high.top();
        //分别为n,n
        else{
            double ans=high.top()+low.top();
            return ans/2.0;
        }
    }
};

复杂度分析：

时间复杂度：，其中添加，寻找中位数。都是基于堆的操作。
空间复杂度：，堆的额外空间。