Minimum Increment to Make Array Unique trong C++

Cho mảng A, mỗi bước chọn A[i] tăng 1. Tìm số bước nhỏ nhất để mọi giá trị trong A đều khác nhau.

Ví dụ: [3,2,1,2,1,7] → 6 (trở thành [3,4,1,2,5,7]).

Giải pháp:

• Sắp xếp A

• Duyệt từ i=1 đến n-1:
  Nếu A[i] ≤ A[i-1]: ret += (A[i-1]+1) - A[i], A[i] = A[i-1]+1

• Trả về ret

Ví dụ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int minIncrementForUnique(vector<int>& A) {       int ret = 0;       sort(A.begin(), A.end());       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;    } }; int main(){ vector<int> v1 = {3,2,1,2,1,7}; Solution ob; cout << ob.minIncrementForUnique(v1); }

Đầu vào

[3,2,1,2,1,7]

Đầu ra

6