使数组在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