945. Minimum Increment to Make Array Unique
给一个整数array : nums
每一个move可以将nums[i]+1
请问最少要几次move才可以使nums里的所有元素都是唯一
思路:
(1)
一开始直觉就是先排序
接着当nums[i]<=nums[i-1]时
ans+=nums[i-1]-nums[i]+1
这样就可以得到答案了
(2)
因为题目限制nums最多有10^5个元素
所以建立一个长度为2*10^5的array : rec
将nums里的元素放到rec里，纪录每个数字分别出现几次
再来去遍历rec，当rec[i]>1时
我们需要把重复的元素放到rec[j]里，其中rec[j]=0
将元素从i放到j需要move j-i次
所以在遍历rec的过程中会出现一下三种情况
dup代表重复的数字出现几次
1.rec[i]==1
什么事都不用做
2.rec[i]>1
dup+=rec[i]-1
ans-=i*(rec[i]-1)
3.rec[i]==0
dup-=1
ans+=i
这样就可以得到答案了
golang code :
func minIncrementForUnique(nums []int) int {
rec:=make([]int,200000)
for _,val:=range nums{
rec[val]++
}
res,dup:=0,0
for key,val:=range rec{
if val>1{
dup+=val-1
res-=(val-1)*key
}else if dup>0 && val==0{
res+=key
dup