Mức tăng tối thiểu để biến mảng trở thành duy nhất trong C ++

Giả sử chúng ta có một mảng các số nguyên A, ở đây một lần di chuyển bao gồm việc chọn bất kỳ A [i] nào và tăng nó lên 1. Chúng ta phải tìm số lần di chuyển ít nhất để mọi giá trị trong A là duy nhất. Vì vậy, nếu đầu vào là [3,2,1,2,1,7], thì đầu ra sẽ là 6, vì sau 6 lần di chuyển, mảng có thể là [3,4,1,2,5,7], nó có thể được hiển thị với 5 lần di chuyển hoặc ít hơn rằng mảng không thể có tất cả các giá trị riêng biệt.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=0

• sắp xếp mảng A

• tạo một tập hợp được gọi là đã truy cập để theo dõi giá trị nào được xem xét trước

• cho tôi trong phạm vi từ 1 đến kích thước của mảng A - 1

  • nếu A [i]

• trả lại 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