※ 引述《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