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