题目描述
给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。
返回使 A 中的每个值都是唯一的最少操作次数。
示例
示例 1：
输入：[1,2,2]
输出：1
解释：经过一次 move 操作，数组将变为 [1, 2, 3]。
示例2：
输入：[3,2,1,2,1,7]
输出：6
解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。
提示：
0 <= A.length <= 40000
0 <= A[i] < 40000
解答方法
方法一：计数
思路
当我们找到一个没有出现过的数的时候，将之前某个重复出现的数增加成这个没有出现过的数。注意，这里 之前某个重复出现的数 是可以任意选择的，它并不会影响最终的答案，因为将 P 增加到 X 并且将 Q 增加到 Y，与将 P 增加到 Y 并且将 Q 增加到 X 都需要进行 (X + Y) - (P + Q) 次操作。
算法
-
首先统计出每个数出现的次数，然后从小到大遍历每个数 x：
如果 x 出现了两次以上，就将额外出现的数记录下来（例如保存到一个列表中）；
如果 x 没有出现过，那么在记录下来的数中选取一个 v，将它增加到 x，需要进行的操作次数为 x - v。
我们还可以对该算法进行优化，使得我们不需要将额外出现的数记录下来。还是以 [1, 1, 1, 1, 3, 5] 为例，当我们发现有 3 个重复的 1 时，我们先将操作次数减去 1 + 1 + 1。接下来，当我们发现 2，4 和 6 都没有出现过时，我们依次将操作次数增加 2，4 和 6。这种优化方法在方法二中也被使用。
参考：https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique/solution/shi-shu-zu-wei-yi-de-zui-xiao-zeng-liang-by-leet-2/
代码
class Solution:
def minIncrementForUnique(self, A: List[int]) -> int:
L = len(A) + 4000
count = [0] * L
for x in A:
count[x]+=1
res = 0
move_cnt = 0
for x in range(L):
if count[x]>=2:
move_cnt += count[x] - 1
res -= x *(count[x] -1 )
elif move_cnt>0 and count[x] == 0:
move_cnt -= 1
res += x
return res
时间复杂度
O(L)，其中 L 的数量级是数组 A 的长度加上其数据范围内的最大值，因为在最坏情况下，数组 A 中的所有数都是数据范围内的最大值。
空间复杂度
O(L)，需要长度 LL 的数组统计每个数出现的次数。
