Java Solution with Two Heaps


  • 0
    public class MedianFinder {
        private PriorityQueue<Integer> min = new PriorityQueue<Integer>();
        private PriorityQueue<Integer> max = new PriorityQueue<Integer>(10, Collections.reverseOrder());
        private Queue<Integer> median = new LinkedList<Integer>();
        // Adds a number into the data structure.
        public void addNum(int num) {
            if (median.isEmpty()) {
                median.offer(num);
            } else {
                if (num < median.peek()) {
                    max.offer(num);
                } else {
                    min.offer(num);
                }
            }
            while (max.size() != 0 && max.size() + 1 > min.size()) {
                min.offer(median.poll());
                median.offer(max.poll());
            } 
            while (min.size() != 0 && max.size() + 1 < min.size()) {
                max.offer(median.poll());
                median.offer(min.poll());
            }
        }
    
        // Returns the median of current data stream
        public double findMedian() {
            if (min.size() == max.size()) {
                return median.peek();
            } else {
                return (median.peek() + min.peek()) / 2.0;
            }
        }
    };
    
    // Your MedianFinder object will be instantiated and called as such:
    // MedianFinder mf = new MedianFinder();
    // mf.addNum(1);
    // mf.findMedian();
    

Log in to reply
 

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