LeetCode 使数组唯一的最小增量

@author:Jingdai @date:2020.10.07

题目描述（945题）

给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。

返回使 A 中的每个值都是唯一的最少操作次数。

示例输入

[1,2,2]

示例输出

1

解释

经过一次 move 操作，数组将变为 [1, 2, 3]

提示：

0 <= A.length <= 400000 <= A[i] < 40000

思路

方法1（排序）

首先对整个数组排序，然后计算每个位置需要加的数。比如数组排序后是 [1, 2, 2, 2, 2, 3] ，如下图左，从前往后遍历，若发现 A[i] <= A[i-1] ，则使 A[i] = A[i-1] + 1 ，相当于进行了 A[i-1] - A[i] + 1 次 move 操作，一直进行了最后，即得到最少的操作次数。有人可能会有疑问，为什么要加 A[i-1] - A[i] + 1 而不是加一，如图右，比如进行到 [1, 2, 3, 4, 2, 3] ，加一还是可能会与前面的数重复，继续加一还是重复，最后还是会加 A[i-1] - A[i] + 1 ，所以这么做相当于一步到位。代码见后面。

方法2 （计数）

由于题目明确说明了数组中值的范围0 <= A[i] < 40000，那可以直接用一个大小为 40000 的数组记录每个元素的个数，这里使用大小为 40001 的 barrel 数组来记录每个元素的个数，为什么加一后面会说。

如下图，首先遍历数组 A ，将数组中元素装入 barrel 数组，记录其每个元素的个数。

然后遍历 barrel 数组，如果发现 barrel[i] > 1 ，代表 barrel[i] 重复了，需要留下一个 barrel[i] ，将剩下的 barrel[i] 加一，即将 move 操作数加 barrel[i] - 1 ，然后 barrel[i+1] 需要加上 barrel[i] - 1 ，这就是之前为什么是 40001 大小的数组了，因为如果 39999 个数大于 1 的话，就会在下标 40000 的位置上存储，所以需要大小为 40001 的数组。

同时我们不需要遍历整个数组，我们遍历数组 A 的时候记录最大值，遍历 barrel 数组时遍历到最大值就不往后遍历了，因为后面都是 0 了。

对于最后一个元素，需要特殊处理，比如最后有5个 x ，则其中1个x不用加（也可以理解为加0），其余4个x分别加1，2，3，4，利用求和公式就是 (n-1)n/2 。然后 move 操作数加上 (n-1)n/2 就行。其实这种方法类似于计数排序，所以本质也是一种排序。代码见下面。

代码

方法1

// first sort public int minIncrementForUnique(int[] A) { int[] sortedA = A.clone(); Arrays.sort(sortedA); int count = 0; for (int i = 1; i < sortedA.length; i++) { if (sortedA[i] <= sortedA[i-1]) { count += sortedA[i-1] - sortedA[i] + 1; sortedA[i] = sortedA[i-1] + 1; } } return count; }

方法2

public int minIncrementForUnique(int[] A) { // we know that 0 <= A[i] < 40000 int[] barrel = new int[40001]; int max = -1; for (int i = 0; i < A.length; i++) { max = max > A[i] ? max : A[i]; barrel[A[i]] ++; } int count = 0; for (int i = 0; i < max+1; i++) { if (barrel[i] > 1) { count += barrel[i] - 1; barrel[i+1] += barrel[i] - 1; } } count += barrel[max+1]*(barrel[max+1]-1)/2; return count; }