My java simple solution using two heap


  • 1
    D
    class MedianFinder {
    PriorityQueue<Integer> minHeap=new PriorityQueue<Integer>();
    PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(5000,Collections.reverseOrder());
    // Adds a number into the data structure.
    public void addNum(int num) {
        if(maxHeap.isEmpty() || num<=maxHeap.peek()) maxHeap.offer(num);
        else minHeap.offer(num);
        if(maxHeap.size()>minHeap.size()+1){
            minHeap.offer(maxHeap.poll());
        }
        else if(minHeap.size()>maxHeap.size()){
            maxHeap.offer(minHeap.poll());
        }
        
    }
    
    // Returns the median of current data stream
    public double findMedian() {
        if(maxHeap.size()>minHeap.size()) return maxHeap.peek();
        else return (maxHeap.peek()+minHeap.peek())/2.0;
    }
    

    };


Log in to reply
 

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