इस ट्यूटोरियल में हमें दो सरणी A और B दी गई हैं। उदाहरण के लिए, हमें A का कोई भी परम्यूटेशन आउटपुट करना है ताकि उन इंडेक्स की संख्या अधिकतम हो जहां A[I] > B[I], उदाहरण के लिए
इनपुट: A = [12, 22, 41, 13], B = [1, 20, 10, 12] आउटपुट: 12, 22, 41, 13 इनपुट: A = [2, 5, 9, 7], B = [1, 12, 4, 54] आउटपुट: 2 7 5 9 कई उत्तर मौजूद हो सकते हैं उस स्थिति में हम बस उनमें से किसी एक को प्रिंट करने जा रहे हैं।
इस समस्या में, हमें उन इंडेक्स को अधिकतम करना है जहां A[i] > B[i], इसलिए हम इस समस्या को लालची तरीके से हल करने जा रहे हैं।
समाधान खोजने का दृष्टिकोण
इस दृष्टिकोण में, हम पहले दोनों सरणियों को सॉर्ट करेंगे; अब हम सरणी B के प्रत्येक इंडेक्स के लिए लालची तरीके से चेक करेंगे कि A[i] इससे अधिक है या नहीं और फिर उस तत्व को एक वेक्टर में रखेंगे।
उदाहरण
#include <bits/stdc++.h> using namespace std; int main(){ int A[] = { 2, 5, 9, 7 }; int B[] = { 1, 12, 4, 54 }; int n = sizeof(A) / sizeof(int); // हमारी सरणियों का आकार vector<pair<int, int> > A_pair, B_pair; /***********************हम तत्व को उसकी स्थिति से जोड़ रहे हैं***********/ for (int i = 0; i < n; i++) A_pair.push_back({A[i], i}); for (int i = 0; i < n; i++) B_pair.push_back({B[i], i}); /***********************************************************************/ /*****हमारे पेयर वेक्टर को सॉर्ट करना********************/ sort(A_pair.begin(), A_pair.end()); sort(B_pair.begin(), B_pair.end()); int i = 0, j = 0, ans[n]; memset(ans, -1, sizeof(ans)); // सभी तत्वों को -1 मान से इनिशियलाइज़ करना vector<int> remaining; // यह हमारे उन तत्वों को स्टोर करेगा जिनका मान B में मौजूद तत्व से कम है। while (i < n && j < n) { // चूंकि हमारी सरणी सॉर्ट है तो यदि हम वर्तमान इंडेक्स में कोई तत्व पाते हैं // जिसका मान B के वर्तमान इंडेक्स से कम है तो // स्वचालित रूप से इसका मान B के अन्य तत्वों से कम होगा // इसलिए हम ऐसे इंडेक्स को remaining में डालते हैं अन्यथा हम ans में तत्व डालते हैं if (A_pair[i].first > B_pair[j].first) { ans[B_pair[j].second] = A_pair[i].first; i++; j++; } else { remaining.push_back(i); i++; } } j = 0; for (int i = 0; i < n; ++i){ // अब यदि उत्तर का कोई इंडेक्स अपरिवर्तित है तो इसका मतलब //हमें उस स्थिति को शेष तत्वों से भरना होगा if (ans[i] == -1){ ans[i] = A_pair[remaining[j]].first; j++; } } for (int i = 0; i < n; i++) // हमारा उत्तर प्रिंट करना cout << ans[i] << " "; return 0; }आउटपुट
2 7 5 9
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम पहले सभी तत्वों को उनके इंडेक्स से जोड़ते हैं ताकि जब हम इसे सॉर्ट करें तो अभी भी उनका पुराना इंडेक्स इसमें हो। हम दोनों पेयर वेक्टर को सॉर्ट करते हैं अब हम लालची तरीके से अपने उत्तर खोजते हैं जैसे ही हम दोनों सरणियों के माध्यम से आगे बढ़ते हैं यदि हमें A_pair का एक इंडेक्स मिलता है जिसका मान B_pair से अधिक है तो हम उसे हमारे ans सरणी में स्टोर करते हैं (और B_pair की स्थिति में) अन्यथा चूंकि हमने दोनों वेक्टर को सॉर्ट किया है, इसलिए हम जानते हैं कि हम A_pair के इस मान का उपयोग नहीं कर पाएंगे, इसलिए हम उस तत्व के इंडेक्स को अपने remaining वेक्टर में डालते हैं अब हम remaining वेक्टर की मदद से सरणी भरते हैं, और फिर उत्तर प्रिंट करते हैं।
निष्कर्ष
इस ट्यूटोरियल में, हम दूसरी सरणी से छोटे मान वाली सरणी के परम्यूटेशन की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण भी सीखा जिसे हमने हल किया। हम यही प्रोग्राम C, Java, Python, और अन्य भाषाओं में भी लिख सकते हैं। आशा है आपको यह ट्यूटोरियल उपयोगी लगा होगा।