题目描述

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

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

样例

输入：[1,2,2]
输出：1
解释：经过一次 move 操作，数组将变为 [1, 2, 3]。

输入：[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

(并查集) $O(n + m)$

1. 使用最朴素的想法，开一个长度为 80000 的数组 used，初始值每个位置都没有使用过。
2. 每次从 used[A[i]] 开始往上寻找第一个没有使用过的位置。
3. 但这样可能导致线性时间的寻找，故使用并查集来优化。初始时每个位置都单独为一个集合。查询时，直接返回 A[i] 所在集合的根结点 x，累加答案后，将 x 与 x + 1 所在集合合并，根结点为 x + 1 所在集合的根结点。

时间复杂度

• 假设并查集操作的时间复杂度为常数，则总时间复杂度为 $O(n + m)$，其中 $m$ 为 max(A[i]) 的两倍。

C++ 代码

class Solution {
public:
    vector<int> f = vector<int>(80010);

    int find(int x) {
        return x == f[x] ? x : f[x] = find(f[x]);
    }

    int minIncrementForUnique(vector<int>& A) {
        int n = A.size(), ans = 0;
        for (int i = 0; i < 80010; i++)
            f[i] = i;

        for (int i = 0; i < n; i++) {
            int x = find(A[i]);
            ans += x - A[i];
            f[x] = x + 1;
        }

        return ans;
    }
};

算法2

(排序) $O(n \log n)$

1. 将所有数字从小到大排序，维护当前可用的值 cur，初始化 cur 为 0。
2. 如果 A[i] < cur，则表示 A[i] 这个数字已经在前边出现过了，需要将 A[i] 增至 cur，然后 cur 自加 1；否则表示 A[i] 一定是可用的，并且更新 cur 为 A[i] + 1。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$，然后仅需一次线性扫描即可统计出答案，故总时间复杂度为 $O(n \log n)$。

C++ 代码

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        int n = A.size(), cur = 0, ans = 0;

        sort(A.begin(), A.end());

        for (int i = 0; i < n; i++) {
            if (A[i] < cur) {
                ans += cur - A[i];
            }
            else {
                cur = A[i];
            }
            cur++;
        }

        return ans;
    }
};