leetcode刷题笔记315题 计算右侧小于当前元素的个数
问题描述：
给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例：
输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素提示：
0 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
//主要使用树状数组两个特性 1.1到x-1的求和 2.x及其后+1
//需要注意的是数的范围，树状数组要求从1开始
object Solution {
def countSmaller(nums: Array[Int]): List[Int] = {
val n = 20001
val tr = Array.fill(n+1)(0)
def lowbit(i: Int): Int = {
return i & (-i)
}
def query(x: Int): Int = {
var res = 0
var i = x
while (i > 0) {
res += tr(i)
i -= lowbit(i)
}
return res
}
def add(x: Int, v:Int): Unit = {
var i = x
while (i <= n) {
tr(i) += v
i += lowbit(i)
}
}
val res = Array.fill(nums.length)(0)
for (i <- (0 to nums.length-1).reverse) {
val x = nums(i) + 10001
res(i) = query(x-1)
add(x, 1)
//println("i: " + i)
}
return res.toList
}
}
var Tr []int
var n = 20001
func Lowbit (x int) int {
return x & (-x)
}
func Query (x int) int {
res := 0
for i := x; i > 0; i -= Lowbit(i) {
res += Tr[i]
}
return res
}
func Add (x , val int) {
for i := x; i <= n; i += Lowbit(i) {
Tr[i] += val
}
}
func countSmaller(nums []int) []int {
Tr = make([]int, 20002)
ans := make([]int, len(nums))
for i := len(nums)-1; i >= 0; i-- {
x := nums[i] + 10001
ans[i] = Query(x - 1)
Add(x, 1)
}
return ans
}