描述
有一个源源不断的吐出整数的数据流,假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构,MedianHolder可以随时取得之前吐出所有数的中位数。
[要求]- 如果MedianHolder已经保存了吐出的N个数,那么将一个新数加入到MedianHolder的过程,其时间复杂度是。
- 取得已经吐出的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; } }