力扣：945. 使数组唯一的最小增量 题解（Java）

题目地址：使数组唯一的最小增量

 

题目描述：

给定整数数组 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

解题思路：

1.题目要求使数组A元素值不重复，遇到重复的值时，使A[i]增加至没有元素的值与它相等。即，例如数组2，2，3，3，4。数组中一个值为2的元素要变成5，一个值为3的元素要变成6；或者一个值为2的元素要变成6，一个值为3的元素要变成5，才能使数组元素的值唯一且增量之和最小

2.统计原数组中每个数字出现的次数，并声明一个容量为80000数组tem用于存储数字出现的次数。因为数组元素的值在[0,40000)之间，且数组最大有40000个元素.极端情况下，可能存在40000个39999。

3.统计完后，从i = 0开始遍历数组A，声明保存增量的变量move。

4.当tem[  A[i]   ]的值存超过1时，查找下一个tem[x]的值为零的x，tem[   A[i]   ]的值减一，令A[i] 的值为x，且tem[x] = 1。并存储A[i]的增量至move中

5.返回move。

代码：

class Solution {
    public int minIncrementForUnique(int[] A) {
        int[] tem = new int[50000];
        for(int i = 0; i < A.length; i++){
            tem[A[i]] += 1;
        }
        int ch = 0, move = 0;
        for(int i = 1; i < A.length;i++){
            if(tem[A[i]] > 1){
                tem[A[i]]--;
                ch = A[i];
                do{
                    move++;
                    ch++;
                } while(tem[ch] != 0);
                tem[ch]++;
            }
        }
        return move;
    }
}