给定一个整数数组 nums，按要求返回一个新数组 *counts。数组 *counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例:
1
2
3
4
5
6
7
| 输入: [5,2,6,1]
输出: [2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.
|
暴力解法（超时）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public List<Integer> countSmaller(int[] nums) {
int n = nums.length;
List<Integer> ans = new ArrayList<>();
for(int i = 0; i < n; i++){
int count = 0;
for(int j = i + 1; j < n; j++){
if(nums[j] < nums[i]){
++count;
}
}
ans.add(count);
}
return ans;
}
}
|
时间复杂度O(n^2)，空间复杂度O(1)。
从暴力解法中可以看出，我们做了许多的重复的统计工作，我们如果从后往前遍历数组，并保存下已经遍历过的数字及它们出现的次数，在下一次遍历时，就不用重复统计。
使用二叉搜索树也可完成插入并统计的功能，我们从右往左依次遍历数组，并构建二叉树。在插入结点的过程中我们可以统计出右侧小于当前结点元素的个数。
在一般的二叉树结点上，我们添加了一个 count 变量来统计小于当前结点 val 值的结点个数。。
递归实现添加结点的算法：
- 当走到右结点，统计根结点和根结点左结点的个数，继续插入并统计根结点右侧是否还有比当前结点值小的结点。
- 当走到左节点或根结点时，计数器加一，继续插入并统计根结点左侧是否还有比当前结点值小的结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
public List<Integer> countSmaller(int[] nums){
Integer[] res = new Integer[nums.length];
Arrays.fill(res, 0);
List<Integer> list = new ArrayList<>();
TreeNode root = null;
for(int i = nums.length - 1; i >= 0; i--){
root = addAndCount(root, new TreeNode(nums[i]), res, i);
}
return Arrays.asList(res);
}
public TreeNode addAndCount(TreeNode root, TreeNode node, Integer[] res, int i){
if(root == null){
root = node;
return root;
}
if(root.val >= node.val){
root.count++ ;
root.left = addAndCount(root.left, node, res, i);
}else{
res[i] += 1 + root.count;
root.right = addAndCount(root.right, node, res, i);
}
return root;
}
class TreeNode{
int val;
int count;
TreeNode left, right;
public TreeNode(int val){
this.val = val;
this.count = 0;
left = null;
right = null;
}
}
}
|
时间复杂度O(nlogn)，空间复杂度O(n)。