Very short one, easy to understand!


  • 0
    Z

    public class MedianFinder {

    private PriorityQueue<Integer> left;
    private PriorityQueue<Integer> right;
    int count;
    double median;
    
    public MedianFinder(){
    	left = new PriorityQueue<Integer>();
    	right = new PriorityQueue<Integer>((a,b)->b-a);
    	count = 0;
    	median = 0;
    }
    
    // Adds a number into the data structure.
    public void addNum(int num) {
        if(count % 2 == 0){
    		right.offer(num);
    		left.offer(right.poll());
    	}
    	else{
    		left.offer(num);
    		right.offer(left.poll());
    	}
    	count++;
    }
    
    // Returns the median of current data stream
    public double findMedian() {
        if(count % 2 == 0) return (left.peek() + right.peek()) / 2.0;
    	return left.peek();
    }
    

    };


Log in to reply
 

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