148ms,17 lines multiset c++ concise solution


  • 0
    Z

    I use multiset to automatically store all the added elements in ascending order,and maintain an iterator it which always points to the size/2th element.

    class MedianFinder {
    public:
        multiset<int> s;
        multiset<int>::iterator it;    
        void addNum(int num) {
            s.insert(num);
            if(s.size()==1)
                it=s.begin();
            else{
                if(*it<=num&&s.size()%2)it++;
                else if(*it>num&&s.size()%2==0)it--;
            }
        }
        double findMedian() {
            return s.size()%2? *it : double(*(++it)+*(--it))/2.0;
        }
    };
    

Log in to reply
 

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