C++ 11-line code using just STL


  • 1
    H

    BST-based solution should be faster, but this code is quite easy to write and understand, hopefully it helps a little.

    The idea is simple: traverse nums backward, cur is a vector storing the accessed elements so far and has been sorted already. So the lower bound of nums[i] in cur, is exactly the number of smaller elements to the right of nums[i] in nums. Keep access nums and update cur and everything's done.

    class Solution {
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> ans, cur;
            for(int i = nums.size()-1; i >= 0; i --) {
                auto iter= lower_bound(cur.begin(), cur.end(), nums[i]);
                int cnt = iter - cur.begin();
                ans.push_back(cnt);
                cur.insert(cur.begin() + cnt, nums[i]);
            }
            reverse(ans.begin(), ans.end());
            return ans;
        }
    };
    

Log in to reply
 

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