Easy to understand C++ solution beats 97%


  • 4
    M

    class MedianFinder {

    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<int> > right;
    

    public:

    // Adds a number into the data structure.
    void addNum(int num) {
        if(left.empty()){
            left.push(num);
            return;
        }
        if(num <= left.top()){
            left.push(num);
            if(left.size()-right.size() > 1){
                right.push(left.top());
                left.pop();
            }
        }
        else{
            right.push(num);
            if(right.size()-left.size() > 1){
                left.push(right.top());
                right.pop();
            }
        }
    }
    
    // Returns the median of current data stream
    double findMedian() {
        if(left.size() == right.size()){
            return (left.top()+right.top())/2.0;
        }
        else if(left.size() > right.size()) return left.top();
        else return right.top();
    }
    

    };


  • 0
    C

    nice solution!


  • 0
    A

    @mightyvoice I wish you offered some explanation for this solution.
    I tried your code with this example [1,2,3]. Basically added these numbers in order and then called findMedian(), it returns 3 and not 2. Could you please check?


  • 0
    N

    @acheiver I think his idea is correct, so basically you have a maxHeap on the left, and minHeap on the right. 1.The difference of the size between two heap should be keep below or equal to one. 2.And all the element on the maxHeap should be smaller than the minHeap elements. Therefore the answer is the top() of these two heap.

    In order to keep the above two points, for each new element, you first decide which heap should it be putted to satisfy the 2, then you put some element back to other heap to satisfy 1.


Log in to reply
 

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