Clear & easy no 2 queues just a multiset


  • 0
    W
    class MedianFinder {
    public:
        typedef multiset< int > Set;
        Set S;
        Set::iterator mi;
        
        MedianFinder() {
            mi = S.end();
        }
        
        // Adds a number into the data structure.
        void addNum(int num) {
            
            S.insert( num );
            
            if( S.size() == 1 ) {
                mi = S.begin();
            }
            else {
                if( ( S.size() & 1 ) == 0 ) {
                    if ( num < *mi )
                        --mi;
                }
                else {
                    if( num >= *mi )
                        ++mi;
                }
            }
        }
    
        // Returns the median of current data stream
        double findMedian() {
            if( ( S.size() & 1 ) ) {
                return *mi;
            }
            else {
                return ( *mi + *next(mi) ) / 2.0;
            }
        }
    };

Log in to reply
 

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