难度: Medium
给你一个整数数组 nums 。每次 move 操作将会选择任意一个满足 0 <= i < nums.length 的下标 i，并将 nums[i] 递增 1。
返回使 nums 中的每个值都变成唯一的所需要的最少操作次数。
示例 1：
输入：nums = [1,2,2] 输出：1 解释：经过一次 move 操作，数组将变为 [1, 2, 3]。
示例 2：
输入：nums = [3,2,1,2,1,7] 输出：6 解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。 可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。
1 <= nums.length <= 1050 <= nums[i] <= 105运行时间: 149 ms
内存: 33.7 MB
class Solution:
def minIncrementForUnique(self, nums: List[int]) -> int:
f = []
s = set()
for num in nums:
if num in s:
f.append(num)
else:
s.add(num)
ans = target = 0
f.sort()
for x in f:
target = max(target, x + 1)
while target in s:
target += 1
ans += target - x
target += 1
return ans
此题解采用了一个分步处理的策略：首先，通过遍历数组并使用一个集合来标记所有已经存在的数字，同时记录所有重复的数字到一个列表中。之后，对这个列表进行排序，然后对于列表中的每个数字，寻找一个尚未使用的最小数字使得该数字变得唯一。这通过逐渐增加一个目标数字并检查它是否被占用来实现。每次找到一个合适的数字后，计算增加的步数，并将此目标数字标记为已使用。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def minIncrementForUnique(self, nums: List[int]) -> int:
f = [] # 存储重复的数字
s = set() # 存储已经存在的数字
for num in nums:
if num in s:
f.append(num) # 记录重复数字
else:
s.add(num) # 添加独特数字
ans = target = 0
f.sort() # 对重复数字排序
for x in f:
target = max(target, x + 1) # 设定最小的可能唯一值
while target in s:
target += 1 # 寻找下一个可用的唯一值
ans += target - x # 计算增加的步数
s.add(target) # 标记此数字已被使用
return ans
使用集合来存储独特的数字可以快速检查一个数字是否已存在，这是因为集合提供了平均时间复杂度为O(1)的查找效率。如果直接在数组内部操作，例如通过搜索或排序来检查唯一性，这将导致更高的时间复杂度，特别是在数组较大时。使用集合可以显著提高算法的效率和响应速度。
在设定重复数字列表`f`的初始值为`x + 1`时，基本思路是尝试将重复的数字`x`增加到它的下一个可能的最小唯一值。这是因为任何小于`x`的值都已经被`x`或之前的数字占据，而`x + 1`是第一个可能未被占据的值，从而使得步数最小化。这样的设置有助于直接定位到可能的最小可用数字，减少不必要的迭代和检查。
对重复数字进行排序可以帮助算法按照从小到大的顺序处理它们，这样可以有效地利用已标记为占用的数字集合`set`，并且避免在寻找下一个可用数字时反复回溯。通过排序，我们可以保证每次处理的数字都是当前未处理的最小值，从而使得寻找下一个可用数字时，能够从前一个已经确定位置的数字顺畅过渡，减少了查找的次数，提高了算法的整体效率。
在最坏的情况下，如果数组中的数字非常密集或有大量重复，`target`可能需要连续增加多次才能找到一个未被使用的数字。这种情况下，每次增加`target`都可能涉及对集合`s`的查找操作，每个查找的时间复杂度为O(1)，但若重复次数多，则整体性能会受到影响。尽管如此，通过使用集合结合排序，该方法通常还是比没有优化的直接处理要高效。