题目
945. 使数组唯一的最小增量 - 力扣（LeetCode）
暴力解法
很容易想到的一个解法是排序，对A[i-1] >= A[i]的情况，把A[i]变成A[i-1] + 1，结果 += 步长即可。但这样做很低效，时间复杂度为O(NlogN)。
class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
if(A.size()<2) return 0;
sort(A.begin(),A.end());
int count = 0;
for(int i = 1; i<A.size();i++) {
if(A[i-1] >= A[i]) {
count += A[i-1]-A[i]+1;
A[i] = A[i-1]+1;
}
}
return count;
}
};
计数补偿法
这个方法是在官方题解里看到的，我把它叫做计数补偿法，因为它的过程是这样的：
遍历数组，对每一个元素计数，计数结果存放在count[]里。计数完成后，遍历count[]，分三种情况
count[i] == 1：已经符合要求，不管它。count[i] > 1：数字重复出现，需要处理。我们需要维护两个变量：一个taken变量，表示需要处理的数字的个数，这里，为了把i出现的次数降为1，我们需要处理count[i] - 1次，所以taken += (count[i] - 1)。另一个需要维护的是ans变量，它也是最终的结果。因为我们是从小到大遍历的，所以我们一定可以用后来的数字替换前面重复出现的数字。这一步我们先将这个需要处理的数字变为0，后面遇到未出现过的数字(即count[j] == 0)时，再把它加回来即可(啰嗦一句，一个i最终变为j，改变量是- i + j)。所以这一步对ans的处理是ans -= i * (count[i] - 1)。count[i] == 0：上面提到这种情况了，数字i未出现过，可以把前面重复的数字变成这个数。更新taken -= 1并补偿ans += i即可。
class Solution {
public int minIncrementForUnique(int[] A) {
int[] count = new int[80000];
for (int x: A) count[x]++;
int ans = 0, taken = 0;
for (int x = 0; x < 80000; ++x) {
if (count[x] >= 2) {
taken += count[x] - 1;
ans -= x * (count[x] - 1);
}
else if (taken > 0 && count[x] == 0) {
taken--;
ans += x;
}
}
return ans;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique/solution/shi-shu-zu-wei-yi-de-zui-xiao-zeng-liang-by-leet-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。