使数组在C ++中唯一的最小增量
假设我们有一个整数数组A，这里的移动包括选择任意A[i]，然后将其递增1。我们必须找到最少的移动次数，才能使A中的每个值唯一。因此，如果输入类似于[3,2,1,2,1,7]，则输出将为6，在移动6次后，数组可能为[3,4,1,2,5,7]，可以通过5次或更少的移动来表明数组不可能具有所有不同的值。
为了解决这个问题，我们将遵循以下步骤-
ret：=0
排序数组A
创建一个称为Visited的集合，以跟踪之前考虑过的值
对于范围从1到数组A–1的i
如果A[i]<A[i–1]，则ret：=ret+（1+A[i–1]）–A[i]，而A[i]：=A[i–1]+1
返回ret。
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
int ret = 0;
sort(A.begin(), A.end());
set <int> visited;
for(int i = 1; i < A.size(); i++){
if(A[i] <= A[i - 1]){
ret+= (A[i - 1] + 1) - A[i];
A[i] = A[i - 1] + 1;
}
}
return ret;
}
};
main(){
vector<int> v1 = {3,2,1,2,1,7};
Solution ob;
cout << (ob.minIncrementForUnique(v1));
}输入项
[3,2,1,2,1,7]
输出结果
6