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