Another java solution using two priority queues


  • 0
    M
    public class MedianFinder {
        Queue<Integer> minHeap = new PriorityQueue<Integer>();
        Queue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>(){
            public int compare(Integer i1,Integer i2){
                if(i1>i2){
                    return -1;
                }else if(i1<i2){
                    return 1;
                }else{
                    return 0;
                }
            }
            });
        // Adds a number into the data structure.
        public void addNum(int num) {
            if(minHeap.size()>0 && maxHeap.size()>0){
                if(num>minHeap.peek()){
                    minHeap.add(num);
                }else{
                    maxHeap.add(num);
                }
            }else{
                maxHeap.add(num);    
            }
            while(Math.abs(maxHeap.size()-minHeap.size())>1){
                if(minHeap.size()>maxHeap.size()){
                    maxHeap.add(minHeap.poll());
                    System.out.println("maxHeap"+maxHeap.peek());
                }else{
                    minHeap.add(maxHeap.poll());
                    System.out.println("minHeap"+minHeap.peek());
                }
            }
        }
    
        // Returns the median of current data stream
        public double findMedian() {
            if(minHeap.size()==maxHeap.size()){
                return (double)((double)minHeap.peek()+(double)maxHeap.peek())/2;
            }else if(minHeap.size()>maxHeap.size()){
                return minHeap.peek();
            }else{
                return maxHeap.peek();
            }
            
        }
    };
    

Log in to reply
 

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