My Java solution (no queue inversion)


  • 0
    Q
    class MedianFinder {
        PriorityQueue<Integer> minQueue = new PriorityQueue<Integer>();
    	PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
    		public int compare(Integer o1, Integer o2) {
    			return o2.compareTo(o1);
    		}
    	});
        public void addNum(int num) {
            if (maxQueue.isEmpty()){
        	    maxQueue.add(num);
            }
            else{
                if (minQueue.isEmpty()){
                    maxQueue.add(num);
                    minQueue.add(maxQueue.poll());
                }
                else{
                    if (num>minQueue.peek()){
                        minQueue.add(num);
                        maxQueue.add(minQueue.poll());
                    }
                    else{
                        maxQueue.add(num);
                    }
                    if(maxQueue.size()-minQueue.size()>1){
                        minQueue.add(maxQueue.poll());
                    }
                }
            }
        }
        public double findMedian() {
           if (maxQueue.size()>minQueue.size()){
        	   return maxQueue.peek();
           }
           return (maxQueue.peek()+minQueue.peek())/(double)2;
        }
    }

  • 0
    Q

    This can be simplified to

    class MedianFinder {
        PriorityQueue<Integer> minQueue = new PriorityQueue<Integer>();
    	PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
    		public int compare(Integer o1, Integer o2) {
    			return o2.compareTo(o1);
    		}
    	});
        public void addNum(int num) {
            if (!minQueue.isEmpty() && num>minQueue.peek()){
                minQueue.add(num);
                maxQueue.add(minQueue.poll());
            }
            else{
                maxQueue.add(num);
            }
            if(maxQueue.size()-minQueue.size()>1){
                minQueue.add(maxQueue.poll());
            }
        }
        public double findMedian() {
           if (maxQueue.size()>minQueue.size()){
        	   return maxQueue.peek();
           }
           return (maxQueue.peek()+minQueue.peek())/(double)2;
        }
    }
    

Log in to reply
 

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