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