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

题意整理

• 需要一个数据结构来存储从数据流吐出的整数。
• 每收到一个整数，都可以得到当前数据结构中所有整数的中位数。

方法一（大顶堆与小顶堆）

1.解题思路

• 初始化一个大顶堆和一个小顶堆。
• 当两个堆大小相等时，将当前元素先入大顶堆，再弹出大顶堆的堆顶元素，将弹出的堆顶元素入小顶堆；如果两个堆大小不相等，则先将当前元素入小顶堆，再弹出堆顶元素入大顶堆。
• 当两个堆大小相等时，数据流总共有偶数个，所以中位数为两个堆堆顶元素之和的一半；当大小不相等时，总共有奇数个，中位数恰好是小顶堆堆顶元素值。

动图展示：

2.代码实现

import java.util.*;
public class Solution {
    /**
     * the medians
     * @param operations int整型二维数组 ops
     * @return double浮点型一维数组
     */
    public double[] flowmedian (int[][] operations) {
        //初始化结果数组
        int len=0;
        for(int[] opera:operations){
            if(opera[0]==2){
                len++;
            }
        }
        double[] res=new double[len];

        //初始化MedianHolder类
        MedianHolder median=new MedianHolder();
        int id=0;
        for(int[] opera:operations){
            //如果opt=1，则加入到结构中
            if(opera[0]==1){
                median.addNum(opera[1]);
            }
            //如果opt=2，则取出当前中位数
            else{
                res[id++]=median.findMedian();
            }
        }

        return res;
    }

    class MedianHolder{
        PriorityQueue<Integer> min;
        PriorityQueue<Integer> max;

        MedianHolder() {
            min=new PriorityQueue<>();
            max=new PriorityQueue<>((o1,o2)->o2-o1);
        }

        //添加当前数字
        public void addNum(int num) {
            if(min.size()==max.size()){
                max.offer(num);
                min.offer(max.poll());
            }
            else{
                min.offer(num);
                max.offer(min.poll());
            }
        }

        //查找当前中位数
        public double findMedian() {
            //如果数据流中没有数字，则返回-1
            if(min.size()==0&&max.size()==0) return -1.0;
            if(min.size()==max.size()){
                return (min.peek()+max.peek())/2.0;
            }
            else{
                return min.peek();
            }
        }
    }
}

3.复杂度分析

• 时间复杂度：堆的插入和弹出操作的时间复杂度都是 ，获取堆顶元素不需要重新调整堆，可以在的时间内找到堆顶元素。所以添加的时间复杂度是，查找的时间复杂度是。
• 空间复杂度：假设数据流的大小为n，最坏情况下，大顶堆或小顶堆的大小为n，所以空间复杂度为。

方法二（维护递增数据流+二分查找）

1.解题思路

核心代码的思路是用list维护一个单调递增的数据流，当有数据进来时，通过二分查找找到这个数在list中的位置，然后插入到这个对应的位置。当list的容量是奇数时，中间的那个数即是数据流的中位数；当list的容量是偶数时，中间两个数的平均值即是数据流的中位数。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * the medians
     * @param operations int整型二维数组 ops
     * @return double浮点型一维数组
     */
    public double[] flowmedian (int[][] operations) {
        //初始化结果数组
        int len=0;
        for(int[] opera:operations){
            if(opera[0]==2){
                len++;
            }
        }
        double[] res=new double[len];

        //初始化MedianHolder类
        MedianHolder median=new MedianHolder();
        int id=0;
        for(int[] opera:operations){
            //如果opt=1，则加入到结构中
            if(opera[0]==1){
                median.addNum(opera[1]);
            }
            //如果opt=2，则取出当前中位数
            else{
                res[id++]=median.findMedian();
            }
        }

        return res;
    }

    class MedianHolder{
        //维护一个单调递增的数据流
        List<Integer> list;

        MedianHolder() {
            list=new ArrayList<>();
        }

        public void addNum(int num) {
            //如果数据流为空或者num大于数据流最大值，则直接添加
            if(list.size()==0||list.get(list.size()-1)<=num){
                list.add(num);
                return;
            }
            //找到num在数据流中的位置，并添加
            int index=binarySearch(list,num);
            list.add(index,num);
        }

        public double findMedian() {
            int n=list.size();
            //如果数据流中没有数字，则返回-1
            if(n==0) return -1.0;
            if(n%2==0){
                return (list.get(n/2)+list.get(n/2-1))/2.0;
            }
            else{
                return (double)list.get(n/2);
            }
        }

        //二分查找
        private int binarySearch(List<Integer> list,int target){
            int l=0,r=list.size()-1;
            while(l<r){
                int mid=l+(r-l)/2;
                if(list.get(mid)>=target){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            return l;
        }
    }
}

3.复杂度分析

• 时间复杂度：添加数据时，使用了二分查找来确定数据的位置，时间复杂度是，然后将数据添加到查找的位置，最坏情况下，需要移动n个元素，所以添加的时间复杂度是，查找中位数时，直接根据索引获取数据，所以查找的时间复杂度是。
• 空间复杂度：假设数据流的大小为n，list需要存储总共n个数据，所以空间复杂度为。