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

发表于 2019-07-03

| 0

| 阅读次数:

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例:
输入: [5,2,6,1]
输出: [2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

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

示例代码(go)

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
}