My c++ solution 160ms


  • 0
    X
    struct classcomp{
    bool operator()(const int& lhs, const int& rhs)const{
        return lhs > rhs;
    }   
    

    };

    class MedianFinder{
    public:

        // Adds a number into the data structure
        void addNum(int num){
            if(big.size() == 0){
                if(small.size() == 0){
                    big.insert(num);
                }else{
                    if(num < *(small.begin())){
                        big.insert(*(small.begin()));
                        small.erase(small.begin());
                        small.insert(num);
                    }else
                        big.insert(num);
                }
                return;
            }else if(small.size() == 0){
                if(big.size() == 0){
                    small.insert(num);
                }else{
                    if(num > *(big.begin())){
                        small.insert(*(big.begin()));
                        big.erase(big.begin());
                        big.insert(num);
                    }else
                        small.insert(num);
                }
                return;
            }
    
            int bigofSmall = *(small.begin());
            int smallofBig = *(big.begin());
            if(num < bigofSmall)
                small.insert(num);
            else if(num > smallofBig)
                big.insert(num);
            else{
                if(big.size() > small.size())
                    small.insert(num);
                else if(big.size() < small.size())
                    big.insert(num);
                else
                    small.insert(num);
            }
            // 调整
            adjust();
        }
    
        // Return the median of current data stream
        double findMedian(){
            if(big.size() == small.size()){
                int Big = *(big.begin());
                int Small = *(small.begin());
                return double(Big+Small) / 2.0;
            }else if(big.size() > small.size()){
                return *(big.begin());
            }else
                return *(small.begin());
        }
    
    private:
        // adjust big and small
        void adjust(){
            int n = big.size() - small.size();
            if(n >= -1 && n <= 1)
                return;
            if(n > 1){
                auto it = big.begin();
                while(big.size() - small.size() > 1){
                    small.insert(*it);
                    it = big.erase(it);                                                                                                                                                                                     
                }
            }else{
                auto it = small.begin();
                while(small.size() - big.size() > 1){
                    big.insert(*it);
                    it = small.erase(it);
                }
            }
        }
    
        multiset<int> big;
        multiset<int, classcomp> small;
    

    };


Log in to reply
 

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