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

  • 0

    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.