题目描述

给定整数数组 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 的数组统计每个数出现的次数。