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

借鉴这个老哥的解题思想https://blog.nowcoder.net/n/1b4531b1265d4fe1b9e4ca31c3c66da1
这是我的实现方法

    //想要取得中位数O(1)
    //中位数怎么求？数据排好序后
    //1.奇数下
    //就是中间那个
    //2.偶数下
    //就是中间两个的平均值
    //可以将这些数据看成左右两半，约定左边的数目容许比右边多1
    //这下好了，奇数下，中位数就是max(left)
    //        偶数下，中位数就是(max(left)+min(left))>>1
    //什么结构能简单获取最值？堆，其中左边用大根堆，右边用小根堆
    //巧妙的数据流动思想:
    //插入一个数
    //    1.左边为空或者小于max(left)，直接插入左边
    //    2.否则，插入右边
    //如果此时右边size=左边size+1，就匀一个来左边
    //如果此时左边size=右边size+2,就匀一个到右边
    public double[] flowmedian (int[][] operations) {
        MedianHolder holder = new MedianHolder();
        ArrayList<Double> list = new ArrayList<>();
        for(int[] opr:operations){
            if(opr[0]==1){
                holder.insert(opr[1]);
            }else{
                list.add(holder.findMedium());
            }
        }
        double[] res = new double[list.size()];
        for(int i = 0;i<list.size();i++){
            res[i] = list.get(i);
        }
        return res;
    }
    public static class MedianHolder{
        PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2)->o2-o1);
        PriorityQueue<Integer> right = new PriorityQueue<>();
        public void insert(int a){
            //插入
            if(left.isEmpty()||a<=left.peek()){
                left.add(a);
            }else{
                right.add(a);
            }
            //匀
            if(right.size()==left.size()+1){
                left.add(right.poll());
            }else if(left.size()==right.size()+2){
                right.add(left.poll());
            }
        }
        public double findMedium(){
            int n = left.size()+right.size();
            if(n==0) return -1;
            if((n&1)==0){//偶数
                return (double)(left.peek()+right.peek())/2;
            }else{
                return (double)left.peek();
            }
        }
    }