问题：给你一个数组A，你选择其中的一个数字，并把它增加1，这就是一次改动。请问至少需要多少次改动，才能使输入的数组的所有数字都变得唯一。假设数组中的数字在0到40000之间。例如，输入数组[3, 2, 1, 2, 1, 7]，我们可以通过6次改动使之变成[3, 4, 1, 2, 5, 7]，由于不存在少于6次的改动，因此输出6。

分析：这是LeetCode的第945题。

解法一：先排序

我们可以先把数组中的数字按照大小排序。如果有重复的数字，这些重复的数字排序之后将排在一起。由于我们的目标是使数组中所有数字都变成唯一，那么当某个数字是i的时候，它的下一个数字至少应该是i+1。如果下一个数字小于i+1，我们就需要增加它，增加的次数即为数字与i+1之间的差值。

例如输入数组[3, 2, 1, 2, 1, 7]，排序之后是[1, 1, 2, 2, 3, 7]。第二个数字和第一个数字重复，因此至少要变成2，需要1次增加。接著第三个数字为2。由于第二个数字已经变成2了，它和第二个数字重复，至少需要变成3，因此也要增加一次。

第三个数字变成3之后，第四个数字至少要变成4（因为我们的目标是让数组成为一个排序的、不含重复数字的数组），因此需要把第四个数字2增加2次。同理，我们也需要把第五个数字3增加2次变成5。第六个数字7和前面的数字没有重复，不需要增加。

总结一下，经过6次增加，我们把输入数组变成了[1, 2, 3, 4, 5, 7]。

下面是这种思路的参考代码：

由于需要对输入的数组排序，假设数组的长度为n，那么时间复杂度是O(nlogn)。

解法二：找出没有出现的数字

我们换一种思路来看这个问题。输入的数组中有可能出现重复的数字，如果有数字重复了，我们需要把重复的数字替换成没有在数组中出现的数字。

例如，在数组[3, 2, 1, 2, 1, 7]中，数字1和2都重复出现了。我们需要把一个1和一个2替换成其他数字使得数组中不含重复的数字。我们应该把重复的那个1替换成什么数字呢？按照题目的规则，我们只能把重复的数字增加，也就是只能把1替换成比1大的数字。同时替换之后数组中不能出现重复的数字，因此应该把1替换成数组中没有的数字。最后，我们希望替换的数字尽可能地小，因为题目求最少的增加次数。这么分析下来，比1大的最小的没有出现在数组中的数字是4。为了把数字1替换成数字4，需要增加3次。

同理，我们可以把一个重复的数字2替换成5。为了把数字2替换成数字5，也需要增加3次。因此总共至少需要6次增加，就可以把数组中的所有数字都变成唯一。

按照前面的分析，我们需要知道哪些数字重复了多少次，哪些数字在数组中没有出现，因此我们需要一个哈希表来统计每个数字出现的次数。由于题目给出了数字出现的范围（最大值为40000），我们可以用一个数组来模拟哈希表。

我们用一个哈希表统计出每个数字出现的数字之后，可以从小到大逐一扫描这个哈希表，一旦遇到重复的数字，可以在后面找到第一个没有在数组中出现的数字（出现的次数为0）。下面是这个思路的参考代码：

在上述代码中，数组numToCount用来冲击每个数字出现的次数。变数j是大于i的最小的没有在数组中出现的数字。

代码中有三个嵌套的循环，看起来时间复杂度是O(n^3)（n为数组numToCount的长度），实际上时间复杂度是O(n)。这是因为在这三个循环中，每次执行的时候都会增加i，有可能增加j。i和j的取值范围都在0到n-1之间，因此最多执行2n次，因此时间时间复杂度是O(n)。

推荐阅读：

相关文章