Re: [閒聊] 每日leetcode已回收

看板Marginalman作者sustainer123 (caster)時間1年前 (2024/06/14 09:41)推噓4(4推 0噓 0→)

留言4則, 4人參與討論串356/1548 (看更多)

※ 引述《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 思路: 直觀上假設nums = [1,2,2] 最少移動一定是[1,2,3] 元素之間只差1 所以先排序假設nums[i] <= nums[i-1] 我們就把nums[i-1]變成nums[i]+1 這樣就是最少移動的情況其實就維持一個公差為1等差數列 Python Code: class Solution: def minIncrementForUnique(self, nums: List[int]) -> int: nums.sort() result = 0 for i in range(1, len(nums)): if nums[i] <= nums[i - 1]: result += nums[i - 1] - nums[i] + 1 nums[i] = nums[i - 1] + 1 return result -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.211.189 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718329303.A.006.html

推

digua

06/14 09:42, 1年前 , 1^F

06/14 09:42, 1^F

推

SecondRun

06/14 09:46, 1年前 , 2^F

06/14 09:46, 2^F

※ 編輯: sustainer123 (223.140.211.189 臺灣), 06/14/2024 09:47:21

推

CP3isgood

06/14 09:49, 1年前 , 3^F