2 PriorityQueue Solution


  • 0
    M
    public class MedianFinder {
    	Queue<Integer> left, right;
    	public MedianFinder() {
    		left = new PriorityQueue<>(Collections.reverseOrder());
    		right = new PriorityQueue<>();
    	}
    	
    	public void addNum(int num) {
    		if (left.isEmpty() || num <= left.peek()) left.offer(num);
    		else right.offer(num);
    		if (left.size() > right.size() + 1) {
    			right.offer(left.poll());
    		} else if (left.size() < right.size()) {
    			left.offer(right.poll());
    		}
    	}
    	
    	public double findMedian() {
    		int size = left.size() + right.size();
    		if (size % 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.