有多少小于当前数字的数字
有多少小于当前数字的数字
给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
法一 暴力
对于数组中的每一个值，我们都去遍历一遍数组，算出多少个比它小的
func smallerNumbersThanCurrent(nums []int) (ans []int) {
for _,v := range nums{
n:=0
for _,v2:=range nums{
if v2法二 排序
创建一个结构体pair，里面存数组中的某个数值和这个数值的位置，将这么一个结构体的数组排序后，对于每一个元素，向前找到第一个与它不一样的，就能知道有多少比它小的
type pair struct{
val int
index int
}
func smallerNumbersThanCurrent(nums []int) []int {
n:=len(nums)
data:=make([]pair,n)
for i:=0; i法三 计数排序
因为数组元素大小不超过100，所以我们开一个101大小的数组data，data[i]表示i出现的次数
对i来说，小于它的数就是data[0]到data[i-1]的总和
func smallerNumbersThanCurrent(nums []int) []int {
data:=[101]int{0}
max:=-1
for _,v := range nums{
data[v]++
if v>max{
max=v
}
}
for i:=1; i<=max; i++{
data[i]=data[i]+data[i-1]
}
ret:=make([]int,len(nums))
for i:=0; i