33 ms JAVA solution, optimization is important


  • 0
    Q

    maintain a left max heap and a right min heap, manage the size that left heap is always equal or one larger than right heap. It seems long, but it is really simple.

    public class MedianFinder {
        PriorityQueue<Integer> right = new PriorityQueue<>();
        PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());
        // Adds a number into the data structure.
        public void addNum(int num) {
            int ls = left.size();
            int rs = right.size();
            if (ls == 0) {
                left.offer(num);
            } else if (rs == 0) {
                Integer lMax = left.peek();
                if (lMax <= num) {
                    right.offer(num);
                } else {
                    right.offer(left.poll());
                    left.offer(num);
                }
            } else {
                Integer lMax = left.peek();
                Integer rMin = right.peek();
                if (ls == rs) {
                    if (num <= rMin) {
                        left.offer(num);
                    } else {
                        left.offer(right.poll());
                        right.offer(num);
                    }
                } else {
                    if (num >= lMax) {
                        right.offer(num);
                    } else {
                        right.offer(left.poll());
                        left.offer(num);
                    }
                }
            }
        }
    
        // Returns the median of current data stream
        public double findMedian() {
            if (left.size() == 0) {
                return 0.0;
            }
            if (left.size() == right.size()) {
                return ((double)left.peek()+(double)right.peek())/2;
            } else {
                return left.peek();
            }
        }
    };

Log in to reply
 

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