2024-04-13：用go语言，给定一个整数数组 `nums`， 请编写一个函

2024-04-13：用go语言，给定一个整数数组，

nums

请编写一个函数，返回一个新的数组。

counts

满足以下条件：对于每个，

nums[i]

表示在右侧且比小的元素数量。

counts[i]

nums[i]

nums[i]

输入：nums = [5,2,6,1]。

输出：[2,1,1,0] 。

答案2024-04-13：

来自左程云。

灵捷3.5

大体过程如下：

给定一个整数数组，首先创建一个与大小相同的临时数组，并将的元素复制到中。然后对进行排序，得到按升序排列的新数组。

nums

nums

sorted

nums

sorted

sorted

接下来，创建一个映射，用于记录每个数在排序后数组中的排名。遍历排序后的数组，将排名存储到中。注意，排名从1开始。

rank

rank

接着创建一个数组，长度为，并定义一个函数，它可以计算一个数的二进制表示中最低位的1的值。再定义一个函数，用于查询比给定排名小的元素数量。函数内部使用循环将数组的前缀和累加到结果中，直到排名为0。还定义一个函数，用于更新数组中对应排名的计数值。

bit

n+2

lowbit

query

bit

update

bit

然后创建一个结果数组，初始化为全0。从右向左遍历原始数组，获取当前元素在排序后数组中的排名，通过调用函数获得在当前元素右侧且小于它的元素数量，并将结果存储到中。同时，调用函数更新数组中排名为的计数值。

ans

nums

r

query

ans

update

bit

r

最后返回结果数组。

ans

总的时间复杂度为O(nlogn)，其中n为数组的大小，主要由排序操作决定。总的额外空间复杂度为O(n)，用于存储临时数组和映射等辅助空间。

Go完整代码如下：

packagemain
import(
"fmt"
"sort"
)
funccountSmaller(nums[]int)[]int{
n:=len(nums)
sorted:=make([]int,n)
copy(sorted,nums)
sort.Ints(sorted)
rank:=make(map[int]int)
fori,num:=rangesorted{
rank[num]=i+1
}
bit:=make([]int,n+2)
lowbit:=func(xint)int{
returnx&-x
}
query:=func(xint)int{
res:=0
forx>0{
res+=bit[x]
x-=lowbit(x)
}
returnres
}
update:=func(xint){
forx<=n+1{
bit[x]++
x+=lowbit(x)
}
}
ans:=make([]int,n)
fori:=n-1;i>=0;i--{
r:=rank[nums[i]]
ans[i]=query(r-1)
update(r)
}
returnans
}
funcmain(){
nums:=[]int{5,2,6,1}
fmt.Println(countSmaller(nums))
}

Python完整代码如下：

#-*-coding:utf-8-*-
defcount_smaller(nums):
n=len(nums)
sorted_nums=sorted([(num,i)fori,numinenumerate(nums)])
rank={sorted_nums[i][0]:i+1foriinrange(n)}
bit=[0]*(n+2)
deflowbit(x):
returnx&-x
defquery(x):
res=0
whilex>0:
res+=bit[x]
x-=lowbit(x)
returnres
defupdate(x):
whilex<=n+1:
bit[x]+=1
x+=lowbit(x)
ans=[0]*n
foriinrange(n-1,-1,-1):
r=rank[nums[i]]
ans[i]=query(r-1)
update(r)
returnans
nums=[5,2,6,1]
print(count_smaller(nums))