इस समस्या में, हमें m और n आकार के पूर्णांक arr1[] और arr2[] के दो सरणियाँ दी गई हैं। हमारा काम यह पता लगाना है कि क्या कोई सरणी किसी अन्य सरणी का सबसेट है - जोड़ा गया तरीका 3 ।
दोनों सरणियाँ arr1[] और arr2[] अव्यवस्थित हैं और इनमें अलग-अलग तत्व हैं।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
Input : arr1[] = {5, 2, 1, 6, 8, 10}, arr2[] = {6, 2, 1}
Output : arr2 is a subset of 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[]