सी++ में सीक्वेंस बढ़ाने के लिए न्यूनतम स्वैप

मान लीजिए कि हमारे पास समान गैर-शून्य लंबाई के दो पूर्णांक अनुक्रम A और B हैं। हम तत्वों ए [i] और बी [i] को स्वैप कर सकते हैं। हमें यह ध्यान रखना होगा कि दोनों तत्व अपने-अपने क्रम में एक ही सूचकांक स्थिति में हैं। कुछ संख्या में स्वैप पूरा करने के बाद, ए और बी दोनों सख्ती से बढ़ रहे हैं। दोनों अनुक्रमों को सख्ती से बढ़ाने के लिए हमें स्वैप की न्यूनतम संख्या का पता लगाना होगा।

तो अगर इनपुट ए =[1,3,5,4] और बी =[1,2,3,7] जैसा है, तो जवाब 1 होगा, अगर हम ए [3] को बी [3] के साथ स्वैप करते हैं, तो अनुक्रम ए =[1,3,5,7] और बी =[1,2,3,4] होंगे, दोनों सख्ती से बढ़ रहे हैं।

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

• n :=एक सरणी का आकार, दो सरणियों को स्वैप करें और प्रत्येक के आकार का कोई स्वैप न करें

• 1 को swapCnt में और 0 को noSwapCnt में डालें

• मैं के लिए 1 से n - 1 की सीमा में

  • swapCnt[i] :=n और noSwapCnt :=n

  • अगर ए [i]> ए [i – 1] और बी [i]> बी [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] :=न्यूनतम स्वैपCnt[i], 1 + noSwapCnt[i – 1]

    • noSwapCnt[i] :=न्यूनतम स्वैपCnt[i – 1], noSwapCnt[i]

• कम से कम स्वैपCnt[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