C++ implement with STL lower_bound, AC


  • 0
    G
    class Solution {
    public:
    vector<int> countSmaller(vector<int>& nums) {
        if(nums.size() < 1)
        return vector<int>(0);
        
        int n = nums.size();
        vector<int> rightNums, ret(n);
        for(int i=n-1; i>=0; --i) {
            if(rightNums.empty()) {
                rightNums.push_back(nums[i]);
                ret[i] = 0;
            } else {
                auto iter = lower_bound(rightNums.begin(), rightNums.end(), nums[i]);
                ret[i] = iter - rightNums.begin();
                
                rightNums.push_back(0);
                for(int j=rightNums.size()-2; j>=ret[i]; --j)
                    rightNums[j+1] = rightNums[j];
                rightNums[ret[i]] = nums[i];
            }
        }
        return ret;
    }
    

    };


  • 6

    After removing all the pointless stuff and with proper insertion:

    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> rightNums, ret(n);
        for(int i=n-1; i>=0; --i) {
            auto iter = lower_bound(rightNums.begin(), rightNums.end(), nums[i]);
            ret[i] = iter - rightNums.begin();
            rightNums.insert(iter, nums[i]);
        }
        return ret;
    }
    

    Still has the same poor runtime complexity, of course. Though, wow, using rightNums.insert does get the time down from 1232ms to 64ms.


  • 0
    T

    This is still O(n^2), right? Cause insert has linear time complexity.


  • 0

    @TonyLic Yes.


Log in to reply
 

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