My accepted C++ solutions using double heaps 384ms and easy understand


  • 0
    M

    class MedianFinder {
    public:

    // Adds a number into the data structure.
    void addNum(int num) {
        if(maxheap.empty()||num<=*(maxheap.begin())){
            maxheap.insert(num);
        }
        else {
            minheap.insert(num);
        }
        if(maxheap.size()>minheap.size()+1)
        {
            minheap.insert(*(maxheap.begin()));
            maxheap.erase(maxheap.begin());
        }
        else if(maxheap.size()<minheap.size())
        {
            maxheap.insert(*(minheap.begin()));
            minheap.erase(minheap.begin());
        }
    
    }
    
    // Returns the median of current data stream
    double findMedian() {
        if(maxheap.size()==minheap.size())
        {
            return (*(maxheap.begin())+*(minheap.begin()))/2.0;
        }
        else
        {
            return (*maxheap.begin());
        }
    }
    

    private:
    multiset<int,greater<int>> maxheap;
    multiset<int> minheap;
    };


Log in to reply
 

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