C++ solution using Multiset


  • 0
    D

    Here multiset is used, only trick is that keep track of middle element when a new element is inserted.
    if new element is greater of equal to middle element and number of element is now even then after inserting increment the middle, similarly if new element is smaller and number of element is odd then decrement middle.

    here is c++ code

    class MedianFinder {
    public:
        /** initialize your data structure here. */
        multiset<int> set;
        int n;
        multiset<int>::iterator mid;
        MedianFinder() {
            set.clear();
            n=0;
            mid = set.end();
        }
        
        void addNum(int num) {
            set.insert(num);
            n++;
            if(n==1){
                mid = next(set.begin(), n/2);
            }
            else{
                if(n%2 == 0 and num >= *mid) mid++;
                else if(n%2 == 1 and num< *mid) mid--;
            }
            
        }
        
        double findMedian() {
            
            auto mid_back = prev(mid, 1-n%2);
            double medi = ((double)(*mid) + (double)(*mid_back))/2;
            return medi;
        }
    };
    
    /**
     * Your MedianFinder object will be instantiated and called as such:
     * MedianFinder obj = new MedianFinder();
     * obj.addNum(num);
     * double param_2 = obj.findMedian();
     */
    

Log in to reply
 

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