Java solution, use max-heap and min-heap


  • 0

    PriorityQueue<Integer> large;
    PriorityQueue<Integer> small;

    public MedianFinder() {
        large = new PriorityQueue<Integer>();
        small = new PriorityQueue<Integer>(new Comparator<Integer>(){
            public int compare(Integer i1, Integer i2){
                return i2 - i1;
            }
        });
    }
    
    public void addNum(int num) {
        large.add(num);
        small.add(large.poll());
        if(large.size() < small.size()){
            large.add(small.poll());
        }
    }
    
    public double findMedian() {
        if(small.size() == large.size()){
            return (double)( small.peek() + large.peek() ) / 2;
        }
        else{
            return large.peek();
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.