945.Minimum Increment to Make Array Unique

Tags:Medium Array

Links: https://leetcode.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:

1. 0 <= A.length <= 40000
2. 0 <= A[i] < 40000

---

最开始只想到了暴力解法，发现再中文是可以AC，但是时间效率很不理想，1800多ms，在英文直接TLE。

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<int> d(80001, 0);
        for (auto e : A) ++d[e];
        int cost = 0;
        for (int i = 0; i < 40001; ++i) {
            if (d[i] >= 2) {
                for (int j = 1; j < 80001; ++j) {
                    int next = i + j;
                    if (next <= 80000 && !d[next]) {
                        ++d[next];
                        cost += j; break;
                    }
                }
                --d[i];
                --i;
            }
        }

        return cost;
    }
};

分析一下上上面的程序主要是在查找下一个可行的位置上花费了时间，那么如果把寻找位置的过程分解开来呢。

如果一个数 x 出现了 c 次，当 c > 1 时，必然要对 c-1 个 x 执行 move 操作，以使得 x 在整个数组中具有唯一性。 那么对于 c-1 个 x+1 如何处理呢？ 那当然是按照上述步骤继续处理，直到数组中的元素两两不相等： 当 c-1 > 1 时，必然对 c-2 个 x+1 执行move操作，以使得 x+1 在整个数组中具有唯一性。

因为给出的元素不会超过 40000，所以操作之后的最大元素不会超过80000。 设 maxValue 为操作之后的最大值。鉴于 maxValue 并不大我们可以使用hash数组来统计数组中每个元素的格数。之后我们遍历该数组并记录move操作的次数即可。 以 [3,2,1,2,1,5] 为例， 首先对次数进行统计，如下图所示

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<int> d(80005, 0);
        for (auto e : A) ++d[e];
        int cost = 0;
        for (int i = 0; i < 80001; ++i) {
            if (d[i] > 1) {
                int delat = d[i] - 1;
                cost += delat;
                d[i] = 1;
                d[i + 1] += delat;
            }
        }

        return cost;
    }
};

时间复杂度是$O(n + m)$。

第二种方法：排序，时间复杂度$O(n \log n)$

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        sort(A.begin(), A.end());
        int cost = 0;
        for (int i = 1; i < A.size(); ++i) {
            int diff = A[i - 1] - A[i] + 1;
            cost += max(0, diff);
            A[i] += max(0, diff);
        }

        return cost;
    }
};