LeetcodeT945

//[945]使数组唯一的最小增量
//给定整数数组 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
//
// Related Topics 数组

这种题目的最小/最少个人觉得具有迷惑性，比如 1 2 1 3这样的数据，无论是把1+3->4 还是 1+2->3 再把原来的3+1->4 答案都是一样的，没有必要将3留在自己的顺序上。

刚开始想通过不排序的方式尝试下，卡在 56 / 59 个通过测试用例超时了。

    public int minIncrementForUnique(int[] A) {
        Set<Integer> set = new HashSet<>();
        int count = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; ; j++) {
                if (!set.contains(A[i] + j)) {
                    count += j;
                    set.add(A[i] + j);
                    break;
                }
            }
        }
        return count;
    }

最终A题代码，排序之后保证当前位置比前面的大就行，因为数字不能变小，所以比较当前数字与前面位置的加一哪个大，较大的数字就是当前位置的值。（如 3、2,取max（3+1,2），将2加到4保存。3、5，取max(3+1,5)，5不变）。

public int minIncrementForUnique(int[] A) {

    Arrays.sort(A);
    int count = 0;
    for (int i = 0; i < A.length; i++) {
        if (i != 0) {
            int t = Math.max(A[i], A[i - 1] + 1);
            count += t - A[i];
            A[i] = t;
        }
    }
    return count;
}