[Java] concise solution


  • -1
    public class MedianFinder {
        PriorityQueue<Integer> min;
        PriorityQueue<Integer> max;
        
        /** initialize your data structure here. */
        public MedianFinder() {
            min = new PriorityQueue<>();
            max = new PriorityQueue<>(1000, Collections.reverseOrder());
        }
        
        public void addNum(int num) {  // This part seems verbose but it calls offer() and poll() as less as possible
            if(max.isEmpty()) max.offer(num);
            else if (num <= max.peek()) {
                max.offer(num);
                if (max.size() > min.size() + 1) {
                    min.offer(max.poll());
                }
            } else {
                min.offer(num);
                if (min.size() > max.size()) {
                    max.offer(min.poll());
                }
            }
        }
        
        public double findMedian() {
            return (max.size() == min.size()) ? (max.peek() + min.peek()) / 2.0 : max.peek();
        }
    }
    
    

  • 0

    I submitted it three times, it beat 35%, 10%, and 53%.


  • 0

    @ManuelP Every time it's different. Weird.


Log in to reply
 

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