12 lines c++ O(NlgN)


  • 0
    L
    struct TreeNode {
        int val, smaller;
        TreeNode *left, *right;
        TreeNode(int val, int smaller) : val(val), smaller(smaller), left(NULL), right(NULL) {}
    };
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res(nums.size());
        function<int(TreeNode*&, int)> insert = [&](TreeNode*& root, int key){return !root ? root = new TreeNode(key, 0), 0 : root->val>key ? ++root->smaller,insert(root->left, key) : insert(root->right, key)+root->smaller+(root->val!=key);};
        TreeNode *root = NULL;
        for (int i = nums.size() - 1; i >= 0; --i) res[i] = insert(root, nums[i]);
        return res;
    }

Log in to reply
 

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