การเพิ่มขั้นต่ำเพื่อทำให้อาร์เรย์ไม่ซ้ำกันใน C++

สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม A ในที่นี้ การย้ายประกอบด้วยการเลือก A[i] ใดๆ และเพิ่มขึ้นทีละ 1 เราต้องหาจำนวนการเคลื่อนไหวน้อยที่สุดเพื่อให้ทุกค่าใน A ไม่ซ้ำกัน ดังนั้นหากอินพุตเป็น [3,2,1,2,1,7] ผลลัพธ์จะเป็น 6 หลังจาก 6 ย้ายอาร์เรย์อาจเป็น [3,4,1,2,5,7] โดยสามารถแสดงได้ไม่เกิน 5 ท่า ซึ่งเป็นไปไม่ได้ที่อาร์เรย์จะมีค่าที่แตกต่างกันทั้งหมด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ret:=0

• จัดเรียงอาร์เรย์ A

• สร้างชุดหนึ่งเรียกว่า visit เพื่อติดตามว่าค่าใดถูกพิจารณาก่อน

• สำหรับฉันอยู่ในช่วง 1 ถึงขนาดของอาร์เรย์ A – 1

  • ถ้า 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]

ผลลัพธ์

6