32ms easy-to-understand java solution


  • 12
    L
    class MedianFinder {
    private Queue<Integer> maxHeap = new PriorityQueue(new Comparator<Integer>(){
       @Override
       public int compare(Integer i1, Integer i2){
           return Integer.compare(i2, i1);
       }
    });
    private Queue<Integer> minHeap = new PriorityQueue(new Comparator<Integer>(){
       @Override
       public int compare(Integer i1, Integer i2){
           return Integer.compare(i1, i2);
       }
    });
    
    // Adds a number into the data structure.
    public void addNum(int num) {
        minHeap.offer(num);
        maxHeap.offer(minHeap.poll());
        
        //if(maxHeap.size() > minHeap.size())
        if(maxHeap.size() - minHeap.size() == 1){
            minHeap.offer(maxHeap.poll());
        }
    }
    
    // Returns the median of current data stream
    public double findMedian() {
        return minHeap.size() > maxHeap.size()
             ? (double)minHeap.peek()
             : (minHeap.peek() + maxHeap.peek())/2.0;
    }
    

    };


  • 0
    W

    i like this answer, it is easy and clear.


  • 0
    S

    said in 32ms easy-to-understand java solution:

    private Queue<Integer> maxHeap = new PriorityQueue

    Initialization of the heaps can be simplified:

    private Queue<Integer> minHeap = new PriorityQueue<>();
    private Queue<Integer> maxHeap = new PriorityQueue<>(11, Collections.reverseOrder());
    

    11 is the default initial capacity used by PriorityQueue implementation.


  • 1
    L

    @s Just personal preference. I always like explicitly specify the comparator even though sometimes it is redundant. I feel that will make the code clear to the programmer at all levels.


Log in to reply
 

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