3/22题解

1.给定整数数组 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 操作是不能让数组的每个值唯一的。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique
方法一：计数
首先统计出每个数出现的次数，然后从小到大遍历每个数 x：
如果 x 出现了两次以上，就将额外出现的数记录下来（例如保存到一个列表中）；
如果 x 没有出现过，那么在记录下来的数中选取一个 v，将它增加到 x，需要进行的操作次数为 x - v。
我们还可以对该算法进行优化，使得我们不需要将额外出现的数记录下来。还是以 [1, 1, 1, 1, 3, 5] 为例，当我们发现有 3 个重复的 1 时，我们先将操作次数减去 1 + 1 + 1。接下来，当我们发现 2，4 和 6 都没有出现过时，我们依次将操作次数增加 2，4 和 6。。

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        int cnt[80000] = { 0 };
        for (int x: A) cnt[x]++;
        int ans = 0, taken = 0;
        for (int x = 0; x < 80000; ++x) {
            if (cnt[x] >= 2) {
                taken += cnt[x] - 1;
                ans -= x * (cnt[x] - 1);
            }
            else if (taken > 0 && cnt[x] == 0) {
                taken--;
                ans += x;
            }
        }
        return ans;
    }
};

方法二：排序

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        sort(A.begin(),A.end());
        int res=0;
        for(int i=1;i<A.size();i++)
        {
            if(A[i]<=A[i-1])//如果后一个数小于等于前一个数，就让他等于前一个数+1，计算移动次数
            {
                int cur=A[i];
                A[i]=A[i-1]+1;
                res+=A[i]-cur;
            }
        }
        return res;
    }
};