leetcode 315. 计算右侧小于当前元素的个数

题解

从后往前遍历 nums,构建二叉搜索树,每个节点要记录其左子树节点的个数 Count

示例代码(go)

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
type Node struct {
Left *Node
Right *Node
Val int
Count int
}

func countSmaller(nums []int) []int {
var root *Node
n := len(nums)
res := make([]int, n)
for i := n-1; i >= 0; i-- {
root = insert(root, nums[i], i, res)
}
return res
}

func insert(root *Node, val, index int, res []int) *Node {
if root == nil {
root = &Node{nil, nil, val, 0}
} else if val <= root.Val {
root.Count++
root.Left = insert(root.Left, val, index, res)
} else {
res[index] += root.Count + 1
root.Right = insert(root.Right, val, index, res)
}
return root
}