315.Count of Smaller Numbers After Self

1- MergeSort

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

class Solution {

    class TreeNode{
        int smallCount;
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int count, int val){
            this.smallCount = count;
            this.val = val;
        }
    }

    public List<Integer> countSmaller(int[] nums) {
        TreeNode root = null;
        Integer[] ret = new Integer[nums.length];
        if(nums == null || nums.length == 0) return Arrays.asList(ret);
        for(int i=nums.length-1; i>=0; i--){
            root = insert(root, nums[i], ret, i, 0);
        }
        return Arrays.asList(ret);
    }

    public TreeNode insert(TreeNode root, int val, Integer[] ans, int index, int preSum){
        if(root == null){
            root = new TreeNode(0, val);
            ans[index] = preSum;
        }
        else if(root.val>val){
            root.smallCount++;
            root.left = insert(root.left, val, ans, index, preSum);
        }
        else{
            root.right = insert(root.right, val, ans, index, root.smallCount + preSum + (root.val<val?1:0));//only adding 1 on preSum if root.val is only smaller than val
        }
        return root;
    }
}

2-Merge

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

归并

归并是如果前后出现交换。那么出现逆序需要修改数组

class Solution {
class NumberIndex {
    int number;
    int index;

    NumberIndex(int number, int index) {
        this.number = number;
        this.index = index;
    }

    NumberIndex(NumberIndex another) {
        this.number = another.number;
        this.index = another.index;
    }
}

public List<Integer> countSmaller(int[] nums) {
    NumberIndex[] cnums = new NumberIndex[nums.length];
    for (int i = 0; i < nums.length; i++) {
        cnums[i] = new NumberIndex(nums[i], i);
    }
    int[] smaller = new int[nums.length];
    cnums = sort(cnums, smaller);
    List<Integer> res = new ArrayList<>();
    for (int i : smaller) {
        res.add(i);
    }
    return res;
}

private NumberIndex[] sort(NumberIndex[] nums, int[] smaller) {
    int half = nums.length / 2;
    if (half > 0) {
        NumberIndex[] rightPart = new NumberIndex[nums.length - half];
        NumberIndex[] leftPart = new NumberIndex[half];
        for (int i = 0; i < leftPart.length; i++) {
            leftPart[i] = new NumberIndex(nums[i]);
        }
        for (int i = 0; i < rightPart.length; i++) {
            rightPart[i] = new NumberIndex(nums[half + i]);
        }
        NumberIndex[] left = sort(leftPart, smaller), right = sort(
                rightPart, smaller);
        int m = left.length, n = right.length, i = 0, j = 0;
        while (i < m || j < n) {
            if (j == n || i < m && left[i].number <= right[j].number) {
                nums[i + j] = left[i];
                smaller[left[i].index] += j;
                i++;
            } else {
                nums[i + j] = right[j];
                j++;
            }
        }
    }
    return nums;
}
}