Re: [閒聊] 每日leetcode

[DJYOSHITAKA (franchouchouISBEST)]

好久沒有在平日早上寫了
剩我是公司的狗了

945. Minimum Increment to Make Array Unique

思路:
先排列
如果遇到某一區間是nums[j]-nums[i]會小於j-i
就代表這個區間必須透過數個move去撐開成[nums[i], nums[i]+1, nums[i]+2, ...]

若nums[j]-nums[i] >= j-i
代表可以reset 重新開始一個新的區間

def minIncrementForUnique(self, nums: List[int]) -> int:
    nums.sort()
    start_i, target_diff, ans = 0, 1, 0
    for i in range(1,len(nums)):
        if (nums[i]-nums[start_i]) < (i-start_i):
            ans += (nums[start_i]+target_diff-nums[i])
            target_diff += 1
        else:
            target_diff = 1
            start_i = i

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.171.3.236 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718327995.A.049.html
※ 編輯: DJYOSHITAKA (1.171.3.236 臺灣), 06/14/2024 09:20:44
推 JIWP: 大師
推 JenniferLope: 大師
→ NCKUEECS: 在公司寫=公司是你的狗
推 sustainer123: 我以後也想在公司刷題
→ digua: 大師