Share my java solution logn to insert, O(1) to query


  • 55
    K

    Not sure why it is marked as hard, i think this is one of the easiest questions on leetcode.

    class MedianFinder {
        // max queue is always larger or equal to min queue
        PriorityQueue<Integer> min = new PriorityQueue();
        PriorityQueue<Integer> max = new PriorityQueue(1000, Collections.reverseOrder());
        // Adds a number into the data structure.
        public void addNum(int num) {
            max.offer(num);
            min.offer(max.poll());
            if (max.size() < min.size()){
                max.offer(min.poll());
            }
        }
    
        // Returns the median of current data stream
        public double findMedian() {
            if (max.size() == min.size()) return (max.peek() + min.peek()) /  2.0;
            else return max.peek();
        }
    };

  • 17
    Y

    With the help of java 8, you can simply write this (no initial capacity needed any more) :

    PriorityQueue<Integer> max = new PriorityQueue(Collections.reverseOrder());
    

  • 0
    H

    Most concise solution, well done!


  • 0
    B

    The code is simple but it's not that easy to come up with this double queues idea.


  • 0
    B

    said in Share my java solution logn to insert, O(1) to query:

    PriorityQueue

    1. PriorityQueue holds one minimum heap inside as its data storage;
    2. here the 'min' queue means it will return the minimum data when calling min.poll(); but actually it stores the left (bigger) half of stream data; on the other hand, the 'max' queue means it returns the maximum data when calling max.poll(), and actually its stores the right(smaller) half. Is it correct?

  • 0
    R

    @biolearning said in Share my java solution logn to insert, O(1) to query:

    it stores the left (bigger) half of stream data;
    on the other hand, the 'max' queue means it returns the maximum data when calling max.poll(), and actually its stores the right(smaller) half

    Usually the sorting is in ascending order, so the bigger half of the numbers is on the right (not left). Other than this, I think your understanding is correct!


  • 0
    This post is deleted!

  • 0
    Z

    whats the running time of this solution ? I have a similar one but it's very slow.


  • 1
    X

    @ZZJJ I have a similar solution. It's slow but easy to implement (without lots of ifs). By writing some if statements to compare num with max.peek() and min.peek(), you can reduce the number of expensive (compared with O(1) peek) offer/poll operations. But I don't think their big-O runtimes are different.


  • 0

    @kennethliaoke said in Share my java solution logn to insert, O(1) to query:

    Not sure why it is marked as hard, i think this is one of the easiest questions on leetcode.

    class MedianFinder {
        // max queue is always larger or equal to min queue
        PriorityQueue<Integer> min = new PriorityQueue();
        PriorityQueue<Integer> max = new PriorityQueue(1000, Collections.reverseOrder());
        // Adds a number into the data structure.
        public void addNum(int num) {
            max.offer(num);
            min.offer(max.poll());
            if (max.size() < min.size()){
                max.offer(min.poll());
            }
        }
    
        // Returns the median of current data stream
        public double findMedian() {
            if (max.size() == min.size()) return (max.peek() + min.peek()) /  2.0;
            else return max.peek();
    

    Nice and concise solution! One very very little improvement of the code (not the algorithm) is that the "else" in the last line could be omitted :)

        }
    };

  • 0
    K

    Did you mean to say in your comment? The min queue actually holds the bigger half of the numbers

    // max queue is always smaller or equal to min queue.


  • 0

    @kikolam I think you are correct. The comment in the original post is misleading. The default ordering in PriorityQueue in Java is ascending. The min queue should hold the larger half while the max queue holds the smaller half. The names are also misleading.


Log in to reply
 

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