इस समस्या में, हमें आकार m और n के दो पूर्णांक सरणियाँ arr1[] और arr2[] दी गई हैं। हमारा कार्य जांचना है कि क्या एक सरणी दूसरी सरणी का उपसमुच्चय है - विधि 3 जोड़ी गई।
दोनों सरणियाँ arr1[] और arr2[] असॉर्टेड हैं और उनमें विशिष्ट तत्व हैं।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट : arr1[] = {5, 2, 1, 6, 8, 10}, arr2[] = {6, 2, 1} आउटपुट : arr2, arr1 का उपसमुच्चय है। समाधान दृष्टिकोण
इस समस्या को हल करने के लिए, हमने यहां कई विधियों पर चर्चा की है। आइए प्रत्येक के कार्य को प्रोग्राम के साथ देखें।
विधि 1
समस्या को हल करने की एक विधि सीधे उपसमुच्चय की जांच करना है। यह नेस्टेड लूप्स का उपयोग करके किया जाता है, बाहरी लूप सरणी arr2[] के प्रत्येक तत्व के लिए और आंतरिक लूप सरणी arr1[] के प्रत्येक तत्व के लिए। हम जांचेंगे कि क्या arr2 का प्रत्येक तत्व arr1 में मौजूद है, यदि हां तो 1 लौटाएं (arr2, arr1 का उपसरणी है) अन्यथा 0 लौटाएं (arr2, arr1 का उपसरणी नहीं है)।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <iostream> using namespace std; bool isSubsetArray(int arr1[], int arr2[], int m, int n){ int j = 0; for (int i = 0; i < n; i++) { for (j = 0; j < m; j++) { if (arr2[i] == arr1[j]) break; } if (j == m) return false; } return true; } int main(){ int arr1[] = {5, 2, 1, 6, 8, 10}; int arr2[] = {6, 2, 1}; int m = sizeof(arr1) / sizeof(arr1[0]); int n = sizeof(arr2) / sizeof(arr2[0]); isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]"; return 0; } आउटपुट
arr2[] is subset of arr1[]
विधि 2
समस्या को हल करने की एक और विधि यह जांचना है कि क्या arr2 के सभी तत्व arr1 में मौजूद हैं। इसे प्रभावी ढंग से करने के लिए, हम सरणी arr1[] को सॉर्ट करेंगे और फिर arr2 के प्रत्येक तत्व के लिए, arr2[] के तत्वों को arr1[] में खोजने के लिए बाइनरी सर्च करेंगे। अब, यदि कोई तत्व नहीं मिलता है, तो 0 लौटाएं (arr2, arr1 का उपसरणी नहीं है) और यदि arr2 के सभी तत्व arr1 में मौजूद हैं, तो 1 लौटाएं (arr2, arr1 का उपसरणी है)।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <bits/stdc++.h> using namespace std; int binarySearch(int arr[], int low, int high, int x){ if (high >= low){ int mid = (low + high) / 2; if ((mid == 0 || x > arr[mid - 1]) && (arr[mid] == x)) return mid; else if (x > arr[mid]) return binarySearch(arr, (mid + 1), high, x); else return binarySearch(arr, low, (mid - 1), x); } return -1; } bool isSubsetArray(int arr1[], int arr2[], int m, int n){ int i = 0; sort(arr1, arr1 + m); for (i = 0; i < n; i++) { if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1) return 0; } return 1; } int main(){ int arr1[] = {5, 2, 1, 6, 8, 10}; int arr2[] = {6, 2, 1}; int m = sizeof(arr1) / sizeof(arr1[0]); int n = sizeof(arr2) / sizeof(arr2[0]); isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]"; return 0; } आउटपुट
arr2[] is subset of arr1[]
विधि 3
समाधान खोजने की एक और विधि पहले दोनों सरणियों arr1[] और arr2[] को सॉर्ट करना है। फिर सरणी arr2[] के सभी तत्वों के लिए जांचें कि क्या वे arr1[] में मौजूद हैं। इसके लिए, हमारे पास एक सीधी विधि है जो दोनों सरणियों में तत्वों के इंडेक्स का उपयोग करती है।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <bits/stdc++.h> using namespace std; bool isSubsetArray(int arr1[], int arr2[], int m, int n){ int i = 0, j = 0; if (m < n) return 0; sort(arr1, arr1 + m); sort(arr2, arr2 + n); while (i < n && j < m){ if (arr1[j] < arr2[i]) j++; else if (arr1[j] == arr2[i]){ j++; i++; } else if (arr1[j] > arr2[i]) return 0; } return (i < n) ? false : true; } int main() { int arr1[] = {5, 2, 1, 6, 8, 10}; int arr2[] = {6, 2, 1}; int m = sizeof(arr1) / sizeof(arr1[0]); int n = sizeof(arr2) / sizeof(arr2[0]); isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]"; return 0; } आउटपुट
arr2[] is subset of arr1[]
विधि 4
एक और विधि, यह जांचने के लिए कि क्या arr2, arr1 का उपसमुच्चय है, हैशिंग का उपयोग करना है। हम arr1 के सभी तत्वों का उपयोग करके एक हैश टेबल बनाएंगे और फिर हैश टेबल में arr2 के तत्वों को खोजेंगे। यदि मान मिलते हैं, तो 1 लौटाएं (arr2, arr1 का उपसमुच्चय है) अन्यथा 0 लौटाएं (arr2, arr1 का उपसमुच्चय नहीं है)।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <bits/stdc++.h> using namespace std; bool isSubsetArray(int arr1[], int arr2[], int m, int n){ set<int> arr1Hash; for (int i = 0; i < m; i++) arr1Hash.insert(arr1[i]); for (int i = 0; i < n; i++) { if (arr1Hash.find(arr2[i]) == arr1Hash.end()) return false; } return true; } int main(){ int arr1[] = {5, 2, 1, 6, 8, 10}; int arr2[] = {6, 2, 1}; int m = sizeof(arr1) / sizeof(arr1[0]); int n = sizeof(arr2) / sizeof(arr2[0]); isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]"; return 0; } आउटपुट
arr2[] is subset of arr1[]
विधि 5
समस्या को हल करने की एक और विधि सेट डेटा संरचना का उपयोग करना है। हम arr1 के सभी मानों के साथ एक नया सेट बनाएंगे और उसकी लंबाई जांचेंगे। फिर हम arr2 के सभी मानों को सम्मिलित करने का प्रयास करेंगे, यदि जोड़ने से लंबाई बदलती है तो arr2, arr1 का उपसमुच्चय नहीं है। यदि arr2 के तत्वों को जोड़ने के बाद लंबाई में कोई परिवर्तन नहीं होता है तो arr2, arr1 का उपसमुच्चय है।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <bits/stdc++.h> using namespace std; bool isSubsetArray(int arr1[], int arr2[], int m, int n){ unordered_set<int> arrSet; for (int i = 0; i < m; i++) { arrSet.insert(arr1[i]); } int setSize = arrSet.size(); for (int i = 0; i < n; i++) { arrSet.insert(arr2[i]); } if (arrSet.size() == setSize) { return true; } else { return false; } } int main(){ int arr1[] = {5, 2, 1, 6, 8, 10}; int arr2[] = {6, 2, 1}; int m = sizeof(arr1) / sizeof(arr1[0]); int n = sizeof(arr2) / sizeof(arr2[0]); isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]"; return 0; } आउटपुट
arr2[] is subset of arr1[]
