剑指offer-63-数据流中位数

思路

• 思路 用两个堆维护中位数

代码

import java.util.*;
public class Solution {
    PriorityQueue<Integer> q1=new PriorityQueue<>((o1,o2)->Integer.compare(o2,o1));
    PriorityQueue<Integer> q2=new PriorityQueue<>();
    public void Insert(Integer num) {
        if(q1.size()==0 ||q2 .size()==0){
            if(q1.size()==0){
                q1.add(num);
            }else{
                q2.add(num);
            }
            return;
        }
        // 与q1堆 比较交换
        if(num<=q1.peek()){
            q1.add(num);
            num=q1.poll();
        }
        // 与q2堆 比较交换
        if(num>q2.peek()){
            q2.add(num);
            num=q2.poll();
        }
        //现在 num介于q1,q2之间
        if(q1.size()<=q2.size()){
            q1.add(num);
        }else{
            q2.add(num);
        }
    }

    public Double GetMedian() {
        double min=q1.size()==0?0:q1.peek();
        double max=q2.size()==0?0:q2.peek();
        if(q1.size()==q2.size()){
            return (min+max)/2;
        }else{
            return min;
        }
    }
}