LeetCode.945.Minimum Increment to Make Array Unique 使数组唯一的最小增量

题目描述

945 Minimum Increment to Make Array Unique
https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique/

Given an array of integers A, a move consists of choosing any A[i], and incrementing it by 1.

Return the least number of moves to make every value in A unique.

Example 1:

Input: [1,2,2]
Output: 1
Explanation:  After 1 move, the array could be [1, 2, 3].

Example 2:

Input: [3,2,1,2,1,7]
Output: 6
Explanation:  After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.

Note:
0 <= A.length <= 40000
0 <= A[i] < 40000

---

解题过程

这道题我只会暴力搜索，看了题解后，发现有各种思路，非常灵活，很不错的一道题。

先排序

首先要搞清楚一个性质，把x以步长1递增为y，无论先后步骤数是不变的。
比如 2 和 3 都重复，分别需要提升为比较大的另外两个数，无论他俩谁先提升，最终的步骤数都一样。

先 O(nlogn) 排序，然后从小到大遍历，遇到重复的，记下来，遇到中间有间隔的，把之前重复的数提升到这个区间内，提升的步骤数就等于区间内的空位对应的值减去记住的重复的数。

这里面要用到一个等差数列求和公式 sn = na1 + n(n-1)d/2 来快速计算。

时间复杂度 O(nlogn)，空间复杂度 O(logn)，快速排序需要额外 logn 的栈空间。

public int minIncrementForUnique(int[] A) {
    if (null == A || A.length < 2) {
        return 0;
    }
    // 快速排序 nlogn
    Arrays.sort(A);
    // 重复个数
    int duplicateCount = 0;
    // 重复数的和，遇到重复数增加其负值，遇到可用的空位增加正值
    int duplicateSum = 0;
    for (int i = 1; i < A.length; i++) {
        if (A[i] > A[i - 1] + 1 && duplicateCount != 0) {
            // A[i-1] 到 A[i] 之间有 A[i] - A[i-1] - 1 个空位可供使用
            int emptyCount = Math.min(duplicateCount, A[i] - A[i-1] - 1);
            duplicateCount -= emptyCount;
            duplicateSum += emptyCount * (A[i-1] +1) + emptyCount * (emptyCount-1) / 2;
        } else if (A[i] == A[i-1]) {
            duplicateCount++;
            duplicateSum += -A[i];
        }
    }
    // 最后可能有还没处理的重复数
    if (duplicateCount != 0) {
        duplicateSum += duplicateCount * (A[A.length-1] + 1) + duplicateCount * (duplicateCount - 1) / 2;
    }
    return duplicateSum;
}

暴力搜索

把数组元素都放入 map 计数，遇到重复的不断加1直到不再重复。
时间复杂度 O(n^2)， 空间复杂度 O(n)

但提交后会超时，遇到超大数组时太慢了，毕竟是一个一个往上加后计算的。

// 暴力，超时
public int minIncrementForUnique_TimeLimitExceed(int[] A) {
    if (null == A || A.length < 2) {
        return 0;
    }

    Map<Integer, Integer> map = new HashMap<>();

    int steps = 0;
    for (int n : A) {
        if (!map.containsKey(n)) {
            map.put(n, 0);
        } else {
            int incr = n + 1;
            while (map.containsKey(incr)) {
                incr++;
            }
            steps += incr - n;
            map.put(incr, 0);
        }
    }
    return steps;
}

---

GitHub代码

algorithms/leetcode/leetcode/_945_MinimumIncrementToMakeArrayUnique.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_945_MinimumIncrementToMakeArrayUnique.java

---