A clean solution using multiset in C++


  • 7

    The key point here is to ensure the midIter always points to the median or if it's even array then to the first of the median.

    the complete solution in C++ as follows.

    class MedianFinder {
    private:
        int size; 
        multiset<int> numsSet;
        multiset<int>::iterator midIter;
    public:
    
        // Adds a number into the data structure.
        void addNum(int num) 
        {
            if(numsSet.empty())
            {
                midIter = numsSet.insert(num);
                size++;
                return ; 
            }
            numsSet.insert(num);
            if((size&1) && num<*midIter) --midIter; 
            else if(!(size&1) && num>=*midIter) ++midIter;
            size++;
        }
    
        // Returns the median of current data stream
        double findMedian() 
        {
            if(size & 1) return *midIter;   
            else return (double)(*midIter+*next(midIter))/2;
        }
    };
    

  • 0
    P

    Smart one!! Given multiset in STL is typically implemented by some balanced BST, the time complexity of insert(), next() is worst case O(logn).
    Actually, the BST-based solution is more natural than the two-heap one. It is also more extensible if we want get other order statistics (e.g. k-th largest) and the median.


Log in to reply
 

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