原题链接在这里：https://leetcode.com/problems/count-of-smaller-numbers-after-self/
题目：
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].
题解：
从右向左扫描数组nums, try to find the position of nums[i] in BST.
For each BST node, it contains its left subtree size count, its duplicate count.
When inserting a new node, returns the sum of smaller count.
Time Complexity: O(n^2). BST不一定balance. Space: O(n).
AC Java:
class Solution {
public List<Integer> countSmaller(int[] nums) {
LinkedList<Integer> res = new LinkedList<>();
if(nums == null || nums.length == 0){
return res;
}
int n = nums.length;
res.offerFirst(0);
TreeNode root = new TreeNode(nums[n - 1]);
root.count = 1;
for(int i = n - 2; i >= 0; i--){
int smallerCount = insert(root, nums[i]);
res.offerFirst(smallerCount);
}
return res;
}
private int insert(TreeNode root, int num){
int smallerCountSum = 0;
while(root.val != num){
if(root.val > num){
root.leftCount++;
if(root.left == null){
root.left = new TreeNode(num);
}
root = root.left;
}else{
smallerCountSum += root.leftCount + root.count;
if(root.right == null){
root.right = new TreeNode(num);
}
root = root.right;
}
}
root.count++;
return smallerCountSum + root.leftCount;
}
}
class TreeNode{
int val;
int count;
int leftCount;
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.val = val;
this.count = 0;
this.leftCount = 0;
}
}