描述

  • 有一个源源不断的吐出整数的数据流,假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构,MedianHolder可以随时取得之前吐出所有数的中位数。
    [要求]

    1. 如果MedianHolder已经保存了吐出的N个数,那么将一个新数加入到MedianHolder的过程,其时间复杂度是
    2. 取得已经吐出的N个数整体的中位数的过程,时间复杂度为
  • 每行有一个整数opt表示操作类型
    若opt=1,则接下来有一个整数N表示将N加入到结构中。
    若opt=2,则表示询问当前所有数的中位数

方法一

思路

  • 列表,排序;本题要求实现数据结构能够随时找出数据流的中位数,所以该数据结构需要依据数据的添加实时更新中位数;
  • 中位数(Median)又称中值,统计学中的专有名词,是按顺序排列的一组数据中居于中间位置的数;对于奇数个取中间值,对于偶数个数据则取中间两个值的平均值;
  • 故可以使用列表来存储数据,并且在每次添加数据时,对列表进行一次升序排序,并找出新列表的中位数,更新中位数的记录;
  • 由于排序需要的时间复杂度,所以如果MedianHolder已经保存了吐出的N个数,那么将一个新数加入到MedianHolder的过程,其时间复杂度是;而中位数是每次添加数据都会更新,所以获取中位数的时间复杂度是
  • 空间复杂度:,由于需要存储所有的数据,所以空间复杂度为
  • 代码如下:
    import java.util.*;
    public class Solution {
      /**
       * the medians
       * @param operations int整型二维数组 ops
       * @return double浮点型一维数组
       */
      class MedianHolder{
          List<Integer> datas = new ArrayList<Integer>();
          double medianNum = -1;
          int size = 0;
          // 添加数据
          public void add(int num){
              // 添加数据
              datas.add(num);
              Collections.sort(datas);
              ++size;
              // 更新中值
              int index = size/2;
              if (size % 2 == 0){
                  medianNum = (datas.get(index) +
                               datas.get(index-1)) / 2.00;
                  return;
              }
              medianNum = datas.get(index);
          }
          // 返回中值
          public double getMedian(){
              return this.medianNum;
          }
      }
      public double[] flowmedian (int[][] operations) {
          // 存储中位数
          List<Double> res = new ArrayList<>();
          MedianHolder holder = new MedianHolder();
          // 遍历命令
          for (int i = 0;i < operations.length;++i){
              if (operations[i][0] == 1){
                  holder.add(operations[i][1]);
              }
              if (operations[i][0] == 2){
                  res.add(holder.getMedian());
              }
          }
          double[] medians = new double[res.size()];
          for (int i = 0;i < res.size();++i){
              medians[i] = res.get(i);
          }
          return medians;
      }
    }

方法二 堆

思路

  • 方法一虽然能够随时找到数据流中的中位数,但是其添加数据的时间复杂度是,过大了,而题目要求的是,所以需要考虑降低程序运行的时间复杂度;

  • 由于本题被划分为堆问题,所以可以考虑使用堆来解决问题,毕竟堆也是可以用来排序的;

  • 由于中位数要求所给数据是已排序的,所以可以将排序数据分为两部分,分别为左边部分left以及右边部分right,两者之间需要满足一下关系:

  • 由于中位数求值需要left的最大值,以及right的最小值,所以对left使用最大堆存储,使用最小堆存储right;
    图片说明

  • 而当满足情况(1)时,中位数medium就是left.max与right.min的平均值,而对于情况(2)则中位数medium为left.max;
    图片说明
    图片说明

  • 那么我们来说说插入的操作吧,首先我们需要确定插入时left与right的情况:
    1.当满足情况(1)时,当插入一个数据num时,数据总数变为奇数,也就是说中位数会变为left.max,此时数据应该插入left中,但是由于left存储的是已排序的左边数据,而num现在无法确定其属于哪一边,所以无法直接将num插入left中,但是我们知道right是一个最小堆,所以我们可以先将num插入right中,此时right堆顶元素是right中的最小值,将其移入left中即可。
    图片说明
    2.当满足情况(2)时,插入一个数据num,数据总数会变为偶数,也就是说中位数变为,此时数据应该插入right中,同样由于不知道num究竟属于哪一边,所以需要先将num插入left,取出最大值max插入right中。
    图片说明

  • 插入数据的时间复杂度:O(logn),每次添加数据时需要调整一次堆结构,时间复杂度为O(logn);

  • 查询中位数的时间复杂度:O(1),中位数在插入数据时就已经计算好了,所以查询的时间为O(1);

  • 空间复杂度为O(n),存储数据。

  • 代码如下:

    import java.util.*;
    public class Solution {
      /**
       * the medians
       * @param operations int整型二维数组 ops
       * @return double浮点型一维数组
       */
      class MedianHolder{
    
          double medianNum = -1;
          int size = 0;
          // 建立最小堆存放排序后的右边的数据,堆顶是右边数据的最小值
          PriorityQueue<Integer> right = new PriorityQueue<>();
          // 建立最大堆,存放排序后左边的数据,堆顶是左边数据的最大值
          PriorityQueue<Integer> left = 
              new PriorityQueue<>((o1,o2) -> o2 - o1);
          // 添加数据
          public void add(int num){
              // 新增一个数,总数量为变为偶数
              if(left.size() > right.size()){
    
                  left.offer(num);
                  right.offer(left.poll());
                  // 更新中位数
                  medianNum = (right.peek() + left.peek()) / 2.0;
                  return ;
              }
              // 新增一个数,总数量变为奇数
              right.offer(num);
              left.offer(right.poll());
              medianNum = left.peek();
              return;
    
          }
          // 返回中值
          public double getMedian(){
              return this.medianNum;
          }
      }
      public double[] flowmedian (int[][] operations) {
          // 存储中位数
          List<Double> res = new ArrayList<>();
          MedianHolder holder = new MedianHolder();
          // 遍历命令
          for (int i = 0;i < operations.length;++i){
              if (operations[i][0] == 1){
                  holder.add(operations[i][1]);
              }
              if (operations[i][0] == 2){
                  res.add(holder.getMedian());
              }
          }
          double[] medians = new double[res.size()];
          for (int i = 0;i < res.size();++i){
              medians[i] = res.get(i);
          }
          return medians;
      }
    }