Count of Smaller Numbers After Self

https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).

To the right of 2 there is only 1 smaller element (1).

To the right of 6 there is 1 smaller element (1).

To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

Thoughts

1. 问比它的数小的个数，可以想到BST中从root到它所有要往左的节点数目和路径上每个节点的左子树数目的和。

2. 节点中除了存值，还存左子树节点数。每次插入一个新节点到左边时，更新parent的这个值

3. 问右边比小的个数，那就从右往左建树，树中即所有在它右边的数

4. 有数重复的情况。因此还要一个dup, 默认应该为1.

Code

class Solution {
    struct TreeNode {
        TreeNode *left, *right;
        int val, scount, dup;
        TreeNode(int x) : val(x), scount(0), dup(1), left(NULL), right(NULL) {}
    };

public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 0);
        if (n == 0) return res;
        TreeNode* root = new TreeNode(nums[n - 1]);
        for (int i = n - 2; i >= 0; i--) {
            int scount = 0;
            insert(root, nums[i], scount);
            res[i] = scount;
        }
        return res;
    }

private:
    void insert(TreeNode *node, int num, int& scount) {
        if (num < node->val) {
            ++node->scount;
            if (!node->left) {
                node->left = new TreeNode(num);
            } else {
                insert(node->left, num, scount);
            }
        } else if (num > node->val) {
            scount += node->scount + node->dup;
            if (!node->right) {
                node->right = new TreeNode(num);
            } else {
                insert(node->right, num, scount);
            }
        } else {
            scount += node->scount;
            ++node->dup;
        }
    }
};

class Solution {
    class TreeNode {
        int val, smallerCount, dup = 1;
        TreeNode left, right;
        TreeNode(int val, int smallerCount) {
            this.val = val;
            this.smallerCount = smallerCount;
        }
    }

    int count = 0;
    private TreeNode insert(TreeNode node, int num, int smallerCount) {
        if (node == null) {
            count = smallerCount;
            return new TreeNode(num, 0);
        }
        if (num < node.val) {
            node.smallerCount++;
            node.left = insert(node.left, num, smallerCount);
        } else if (num > node.val) {
            node.right = insert(node.right, num, smallerCount + node.smallerCount + node.dup);
        } else {
            node.dup++;
            count = smallerCount + node.smallerCount;
        }
        return node;
    }

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        TreeNode root = null;
        for (int i = nums.length - 1; i >= 0; i--) {
            count = 0;
            root = insert(root, nums[i], 0);
            res.add(0, count);
        }

        return res;
    }
}

Analysis

Errors:

1. 忘了加当node.val == nums[i]时的smallerCount.

树balance时, 时间复杂度O(NlgN).

Ver.2

Iterative建树

class Solution {
    class TreeNode {
        int val, dup, smallerCount;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
            dup = 1;
            smallerCount = 0;
        }
    } 

    private int add(TreeNode root, int num) {
        int res = 0;
        TreeNode node = root;
        while (node != null) {
            if (num < node.val) {
                node.smallerCount++;
                if (node.left == null) {
                    node.left = new TreeNode(num);
                    break;
                } else {
                    node = node.left;
                }
            } else if (num > node.val) {
                res += node.smallerCount + node.dup;
                if (node.right == null) {
                    node.right = new TreeNode(num);
                    break;
                } else {
                    node = node.right;
                }
            } else {
                res += node.smallerCount;
                node.dup++;
                break;
            }
        }

        return res;
    }

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums.length == 0) {
            return res;
        }

        TreeNode root = new TreeNode(nums[nums.length - 1]);
        res.add(0);
        for (int i = nums.length - 2; i >= 0; i--) {
            res.add(0, add(root, nums[i]));
        }
        return res;
    }
}