C++에서 배열을 고유하게 만들기 위한 최소 증분

<시간/>

정수 배열 A가 있다고 가정합니다. 여기에서 이동은 A[i]를 선택하고 1씩 증가시키는 것으로 구성됩니다. A의 모든 값을 고유하게 만들기 위해 최소 이동 수를 찾아야 합니다. 따라서 입력이 [3,2,1,2,1,7]과 같으면 출력은 6이 됩니다. 6이 이동하면 배열이 [3,4,1,2,5,7]이 될 수 있기 때문입니다. 어레이가 모든 고유 값을 가질 수 없다는 것을 5회 이하의 이동으로 표시할 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ret:=0
정렬 배열 A
어떤 값이 이전에 고려되는지 추적하기 위해 방문이라는 하나의 집합을 만듭니다.
범위 1에서 배열 A – 1의 크기에 대한 i
- A[i]
반환 반환.

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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]