O(lgn) time solution using Priority Queue in Java


  • 0
    Z
    class MedianFinder {
        
        private final PriorityQueue<Integer> left = new PriorityQueue<Integer>(16, Collections.reverseOrder());
    	private final PriorityQueue<Integer> right = new PriorityQueue<Integer>(16);
    	
        private double med;
    
        // Adds a number into the data structure.
        public void addNum(int num) {
            med = getMedian(num);
        }
    
        // Returns the median of current data stream
        public double findMedian() {
            return med;
        }
        
        // insert current element to the left or right heap and get median so far
    	public double getMedian(final int current) {
    	   final int balance = left.size() - right.size();
    	    double median = med;
    	
    	    // both heaps are of equal size.
    	    if (balance == 0) {
    	        // need to insert in left
    	        if (current < median) {
    	            left.offer(current);
    	            median = left.peek();
    	        }
    	        // need to insert in right
    	        else {
    	            right.offer(current);
    	            median = right.peek();
    	        }
    	    }
    	    // left heap is larger
    	    else if (balance > 0) {
    	        // need to insert in left
    	        if (current < median) {
    	            right.offer(left.poll());
    	            left.offer(current);
    	        }
    	        // need to insert in right
    	        else {
    	            right.offer(current);
    	        }
    	
    	        median = (left.peek() + right.peek()) / 2.0;
    	    }
    	    // right heap is larger
    	    else if (balance < 0) {
    	        // need to insert in left
    	        if (current < median) {
    	            left.offer(current);
    	        }
    	        // need to insert in right
    	        else {
    	            left.offer(right.poll());
    	            right.offer(current);
    	        }
    	
    	        median = (left.peek() + right.peek()) / 2.0;
    	    }
    	
    	    return median;
    	}
    };

  • 0
    S

    I did the same approach using priority queue (heap).

    class MedianFinder {
    
    private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); 
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(); 
    
    public MedianFinder() { 
        minHeap = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return (b - a);
            }
        });   
        maxHeap = new PriorityQueue();
    }
    
    // Adds a number into the data structure.
    public void addNum(int num) {
        if(minHeap.size() == 0 || num <= minHeap.peek()) {
            minHeap.add(num); 
        } else {
            maxHeap.add(num);
        }
        
        balanceHeaps(); 
    }
    
    // Returns the median of current data stream
    public double findMedian() {
        double median = 0; 
        if(minHeap.size() == maxHeap.size()) { 
            median = ((double)minHeap.peek() + (double)maxHeap.peek())/2;
        } else { 
            median = (minHeap.size() > maxHeap.size())? minHeap.peek() : maxHeap.peek(); 
        }
        return median; 
    }
    
    private void balanceHeaps() {
        if(minHeap.size() - maxHeap.size() > 1) { 
            maxHeap.add(minHeap.poll());     
        } else if(maxHeap.size()- minHeap.size() > 1) {
            minHeap.add(maxHeap.poll());
        }
    }
    

    };


Log in to reply
 

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