My java solution with two heaps , any improvement ?


  • 0
    S
      //using two heaps and make sure the size of maxHeap is just 1 greater than the size of miniHeap
      
        PriorityQueue<Integer> maxHeap ;
    	PriorityQueue<Integer> minHeap ;
    	
    	public MedianFinder (){
    		maxHeap = new PriorityQueue<> ();
    		minHeap = new PriorityQueue<> ();
    	}
    	
    	  // Adds a number into the data structure.
        public void addNum(int num) {
        	maxHeap.offer(-num) ;
        	if (maxHeap.size() - minHeap.size() >= 2 ) {    		
        		minHeap.offer(maxHeap.poll() * -1) ;    		
        	} else if (!minHeap.isEmpty() && maxHeap.peek() * - 1 > minHeap.peek()) {
        		int a = maxHeap.poll() * -1 ;
        		int b = minHeap.poll() ;
        		maxHeap.offer(-b) ;
        		minHeap.offer(a) ;
        	}    	
        }
    
        // Returns the median of current data stream
        public double findMedian() {
            if (maxHeap.size() == minHeap.size()) {
            	return (maxHeap.peek() * - 1 + minHeap.peek()) / 2.0 ;
            }      
            return maxHeap.peek() * - 1 ;
        }

Log in to reply
 

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