题意:

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

方法一:暴力解法

  • 使用一个,是一个有序的元素可重复的数据结构,由平衡二叉树实现的,所以添加元素的时间复杂度为.返回中位数时由于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)取出中位数,如果lowhigh的数量都是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;
        }
    }
};

复杂度分析:

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