4

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

 3 years ago
source link: https://iamxcb.com/leetcode-315.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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
}
表情 | 预览
Code 401: 未经授权的操作，请检查你的AppId和AppKey.
Powered By Valine
v1.3.9

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK