मान लीजिए हमारे पास समान गैर-शून्य लंबाई के दो पूर्णांक अनुक्रम 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 := A सरणी का आकार, आकार n के दो सरणीswapCntऔरnoSwapCntबनाएंswapCntमें 1 डालें औरnoSwapCntमें 0 डालेंiको 1 सेn - 1तक लूप करेंswapCnt[i] := nऔरnoSwapCnt := n- यदि
A[i] > A[i - 1] AND B[i] > B[i - 1], तोnoSwapCnt[i] := noSwapCnt[i - 1]swapCnt[i] := swapCnt[i - 1] + 1
- यदि
A[i] > B[i - 1] and 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
