C++ solution using vector


  • 0
    A

    class Solution {
    public:
    vector<int> countSmaller(vector<int>& nums) {
    vector<int> track;
    vector<int> res(nums.size(),0);
    for(int i=nums.size()-1;i>=0;i--) {
    auto it = upper_bound(track.begin(),track.end(),-1nums[i]);
    if(it==track.end()) {
    track.push_back(-1
    nums[i]);
    res[i]=0;
    } else {
    res[i]=distance(it,track.end());
    track.insert(it,-1*nums[i]);
    }
    }
    return res;
    }
    };


  • 0
    X

    similar methods

    class Solution {
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> sorted;
    		vector<int> result;
    		while(nums.size()){
    			int deleted = nums.back();
    			nums.pop_back();
    			auto it = lower_bound(sorted.begin(), sorted.end(), deleted);
    			result.insert(result.begin(), it - sorted.begin());
    			sorted.insert(it, deleted);
    		}
    		return result;
        }
    };
    

Log in to reply
 

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