सी++ में ऐरे को विशिष्ट बनाने के लिए न्यूनतम वेतन वृद्धि

मान लीजिए कि हमारे पास पूर्णांक ए की एक सरणी है, यहां एक चाल में कोई ए [i] चुनना होता है, और इसे 1 से बढ़ाना होता है। हमें प्रत्येक मान को अद्वितीय बनाने के लिए कम से कम चालों को ढूंढना होगा। तो अगर इनपुट [3,2,1,2,1,7] जैसा है, तो आउटपुट 6 होगा, जैसा कि 6 चालों के बाद, सरणी [3,4,1,2,5,7] हो सकती है, यह 5 या उससे कम चालों के साथ दिखाया जा सकता है कि सरणी के लिए सभी अलग-अलग मान होना असंभव है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• रिट:=0

• सॉर्ट एरे ए

• पहले किस मान पर विचार किया जाता है, इस पर नज़र रखने के लिए विज़िट नामक एक सेट बनाएं

• मैं के लिए श्रेणी 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