c++ AC use binary insert, very easy understand


  • 1
    class MedianFinder {
        vector<int> data;
    public:
        MedianFinder() {
            data.clear();
        }
        void addNum(int num) {
            data.insert(lower_bound(data.begin(),data.end(),num), num);
        }
        double findMedian() {
            if(data.size()&1) 
                return data[data.size()/2];
            //else if(data.size()==0) return 0;
            else 
                return (data[data.size()/2]+data[data.size()/2-1])*1.0/2;
        }
    };
    

Log in to reply
 

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