题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

解题思路

1、简单解法：使用ArrayList存数据

（1）数据插入在ArrayList尾部，在获取中位数时使用Collections进行排序（从源码可以看到实际调用的是Arrays.sort，使用的是归并排序）
时间复杂度为：、时间复杂度：

（2）数据插入时进行排序（二分插入），获取中位数时直接获取
时间复杂度为：、时间复杂度：

注意：如果数据不重复，可以考虑使用排序的TreeSet

//获取中位数时排序
import java.util.ArrayList;
import java.util.Collections;
public class Solution {    
    public ArrayList<Integer> list=new ArrayList<>();
    public void Insert(Integer num) {
        list.add(num);
    }
    public Double GetMedian() {
        int size=list.size();
        if(size==0) return new Double(0);
        Collections.sort(list);
        return size%2==0?(list.get(size/2)+list.get(size/2-1))*1.0/2.0:new Double(list.get(size/2));
    }
}

//插入数据时排序
import java.util.ArrayList;
public class Solution {    
    public ArrayList<Integer> list=new ArrayList<>();
    public void Insert(Integer num) {
        int size=list.size();
        if(size==0||list.get(size-1)<=num) list.add(num);
        else{
            //使用二分查找
            int low=0,high=list.size()-1,mid=0;
            while(low<high){
                mid=(low+high)/2;
                if(list.get(mid)<num) low=mid+1;
                else if(list.get(mid)>num) high=mid-1;
                else{
                    low=mid;
                    break;
                }
            }
            list.add(low,num);
        }
    }
    public Double GetMedian() {
        int size=list.size();
        return (size&1)==1? new Double(list.get(size/2)) : (list.get(size/2)+list.get(size/2-1))/2.0;
    }
}

2、大小堆：使用PriorityQueue

（1）使用两个堆的思想：小顶堆存较大的数，从小到大排序；大顶堆用来存较小的数，从大到小排列；
（2）flag作为标志位，值true时表示数据流中数字的个数为偶数（包括初始值0），为false时表示为奇数（为了防止数据量过大，因而使用boolean而不是int类型来表示）
（3）插入的方法：为了保持两个堆的平衡，因而根据数据流中的数字个数分为奇偶数插入
——若数据流中的数字个数分为奇数，先插入到大顶堆，并将大顶堆中的最大值取出并插入到小顶堆
——若数据流中的数字个数分为偶数，先插入到小顶堆，并将小顶堆中的最小值取出并插入到大顶堆
（4）由于flag初始值为true，因此数据流中的数字个数分为奇数时，大顶堆中的数比小顶堆中的数要多一个，因而这种情况下中位数直接是大顶堆的堆顶元素

时间复杂度为：、时间复杂度：

import java.util.PriorityQueue;
public class Solution {
    //小顶堆存较大的数，从小到大排序；大顶堆用来存较小的数，从大到小排列；
    public PriorityQueue<Integer> min=new PriorityQueue<>();//建立小顶堆
    public PriorityQueue<Integer> max=new PriorityQueue<>((o1,o2)->o2-o1);//大顶堆
    boolean flag=true;//偶数个为true
    
    public void Insert(Integer num) {
        if(flag){
            min.offer(num);//将num存入小顶堆（里面是较大的数）
            max.offer(min.poll());//将小顶堆中的最小值取出存入大顶堆
        }else{
            max.offer(num);
            min.offer(max.poll());
        }
        flag=flag?false:true;
    }

    public Double GetMedian() {
        return flag? (min.peek()+max.peek())/2.0 : max.peek()*1.0;
    }
}