Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

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--
        }
   }
   return res
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.34.11 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718373488.A.CB1.html
推 SecondRun: 球內推