Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में दूसरी सरणी से छोटे मान वाली सरणी का परम्यूटेशन


इस ट्यूटोरियल में हमें दो सरणी 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, और अन्य भाषाओं में भी लिख सकते हैं। आशा है आपको यह ट्यूटोरियल उपयोगी लगा होगा।

  1. - C++ में दूसरे ऐरे का उपयोग करके ऐरे तत्वों को अधिकतम करना

    समस्या कथन आकार n के दो ऐरे दिए गए हैं, दूसरे ऐरे के तत्वों का उपयोग करके पहले ऐरे को अधिकतम करें जैसे कि नया बना ऐरे दोनों ऐरे के n महानतम लेकिन अद्वितीय तत्वों को समाहित करे, दूसरे ऐरे को प्राथमिकता देते हुए यानी दूसरे ऐरे के सभी तत्व पहले ऐरे से पहले दिखाई दें। तत्वों के प्रकट होने का क्रम आउटपु

  1. - C++ में बाइनरी ऐरे को पार्टीशन करने के लिए न्यूनतम टॉगल (पहले 0s फिर 1s)

    समस्या कथन केवल 0 और 1 वाले n पूर्णांकों का एक ऐरे दिया गया है। न्यूनतम टॉगल (0 से 1 या इसके विपरीत स्विच) ढूंढें ताकि ऐरे पार्टीशन हो जाए, यानी, उसमें पहले 0s फिर 1s हों। उदाहरण यदि arr[] = {1, 0, 0, 1, 1, 1, 0} तो 2 टॉगल आवश्यक हैं यानी पहले 1 और अंतिम 0 को टॉगल करें। एल्गोरिदम यदि हम प्रश्न क

  1. - C++ में दो बाइनरी ऐरे में न्यूनतम फ्लिप्स ताकि उनका XOR तीसरे ऐरे के बराबर हो

    समस्या कथनआकार n के 0 और 1 वाले तीन ऐरे दिए गए हैं, कार्य पहले और दूसरे ऐरे में बिट्स के न्यूनतम फ्लिप ढूंढना है ताकि पहले और दूसरे ऐरे के i-वें इंडेक्स बिट का XOR तीसरे ऐरे के i-वें इंडेक्स बिट के बराबर हो।कृपया ध्यान दें कि हम ऐरे 1 के अधिकतम p बिट्स और ऐरे 2 के अधिकतम q बिट्स फ्लिप कर सकते हैं। ऐ