C++ এ ক্রমবর্ধমান সিকোয়েন্স করতে ন্যূনতম অদলবদল

ধরুন আমাদের কাছে একই অ-শূন্য দৈর্ঘ্যের দুটি পূর্ণসংখ্যার ক্রম A এবং B আছে। আমরা A[i] এবং B[i] উপাদানগুলিকে অদলবদল করতে পারি। আমাদের মনে রাখতে হবে যে উভয় উপাদানই তাদের নিজ নিজ অনুক্রমে একই সূচক অবস্থানে রয়েছে। কিছু সংখ্যক অদলবদল সম্পন্ন করার পর, A এবং B উভয়ই কঠোরভাবে বৃদ্ধি পাচ্ছে। উভয় ক্রম কঠোরভাবে বৃদ্ধি করার জন্য আমাদের সর্বনিম্ন সংখ্যক অদলবদল খুঁজে বের করতে হবে।

সুতরাং ইনপুট যদি A =[1,3,5,4] এবং B =[1,2,3,7] এর মত হয়, তাহলে উত্তর হবে 1, যদি আমরা A[3] কে B[3] এর সাথে অদলবদল করি, তাহলে ক্রম হবে A =[1,3,5,7] এবং B =[1,2,3,4], উভয়ই কঠোরভাবে বৃদ্ধি পাচ্ছে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=একটি অ্যারের আকার, প্রতিটি n আকারের দুটি অ্যারে swapCnt এবং noSwapCnt তৈরি করুন

• swapCnt-এ 1 এবং noSwapCnt-এ 0 ঢোকান

• 1 থেকে n – 1

  রেঞ্জের জন্য i

  • swapCnt[i] :=n এবং noSwapCnt :=n

  • যদি A[i]> A[i – 1] এবং B[i]> B[i – 1], তাহলে

    • noSwapCnt[i] :=noSwapCnt[i – 1]

    • swapCnt[i] :=swapCnt[i – 1] + 1

  • যদি A[i]> B[i – 1] এবং B[i]> A[i – 1] হয়, তাহলে

    • swapCnt[i] :=ন্যূনতম swapCnt[i], 1 + noSwapCnt[i – 1]

    • noSwapCnt[i] :=ন্যূনতম swapCnt[i – 1], noSwapCnt[i]

• ন্যূনতম swapCnt[n – 1], noSwapCnt[n – 1] ফেরত দিন

উদাহরণ(C++)

আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minSwap(vector<int>& A, vector<int>& B) {
      int n = A.size();
      vector <int> swapCnt(n), noSwapCnt(n);
      swapCnt[0] = 1;
      noSwapCnt[0] = 0;
      for(int i = 1; i < n; i++){
         swapCnt[i] = n;
         noSwapCnt[i] = n;
         if(A[i] > A[i - 1] && B[i] > B[i - 1]){
            noSwapCnt[i] = noSwapCnt[i - 1];
            swapCnt[i] = swapCnt[i - 1] + 1;
         }
         if(A[i] > B[i - 1] && B[i] > A[i - 1]){
            swapCnt[i] = min(swapCnt[i], 1 + noSwapCnt[i - 1]);
            noSwapCnt[i] = min(swapCnt[i - 1], noSwapCnt[i]);
         }
      }
      return min(swapCnt[n - 1], noSwapCnt[n - 1]);
   }
};
main(){
   vector<int> v1 = {1,3,5,4};
   vector<int> v2 = {1,2,3,7};
   Solution ob;
   cout << (ob.minSwap(v1, v2));
}

ইনপুট

[1,3,5,4]
[1,2,3,7]

আউটপুট

1