अगर दो दिए गए सेट असंतुष्ट हैं तो कैसे जांचें?


कठिनाई स्तर आसान
में अक्सर पूछा FactSet वृद्धि कुलिजा नगरो संचालित स्नैपडील
ऐरे द्विआधारी खोज हैश लार्सन एंड टुब्रो खोजना छंटाई

समस्या यह है कि "दो दिए गए सेट असंतुष्ट हैं, तो कैसे जांचें?" कहा जाता है कि मान लीजिए कि आपको दो सेट दिए गए हैं जैसे कि अरै सेट 1 [] और सेट 2 []। आपका काम यह पता लगाना है कि दो सेट डिसऑइंट सेट हैं या नहीं।

उदाहरण

inputSet1[] = {1, 15, 8, 9, 6}
inputSet2[] = {2, 4, 19, 3}
These are Disjoint Sets

व्याख्या

चूंकि दोनों सेट में कोई सामान्य तत्व नहीं हैं, इसलिए वे सेट से असंतुष्ट हैं

inputSet1[] = {2, 1, 6, 9, 7}
inputSet2[] = {2, 4, 19, 3}
These are not Disjoint Sets

व्याख्या

यहां 2 दोनों सेट में एक सामान्य तत्व है, इसलिए वे सेट से असंतुष्ट नहीं हैं।

कलन विधि

  1. डिक्लेयर ए हैशसेट.
  2. सेट 1 के सभी तत्वों को हैशसेट में डालें।
  3. Set2 [] के सभी तत्वों को ट्रेस करें और जांचें कि क्या HashSet में set2 [] के कोई तत्व हैं या नहीं।
    1. अगर इसमें समाहित है, तो गलत है।
  4. सच लौटा दो।

व्याख्या

हमने एक समस्या बयान दिया है जो यह पता लगाने के लिए कहता है कि दिए गए दो सेट असहमति सेट हैं या नहीं। दोनों सेटों को एक सरणी के रूप में दर्शाया गया है। हम एक HashSet का उपयोग करेंगे और HashSet के गुणों को प्राप्त करेंगे। एक HashSet डुप्लिकेट मानों को संग्रहीत करने की अनुमति नहीं देता है।

डिक्लेयर ए  बूलियन फ़ंक्शन जो केवल या तो सही या गलत देता है। हम उस बूलियन फ़ंक्शन के लिए दो सरणियाँ पास करेंगे और पहली चीज़ जो यह करेगी वह सेट 1 [] के मूल्य को HashSet में संग्रहीत कर रहा है और set1 के प्रत्येक मूल्य को संग्रहीत करने के बाद [] यह जाँच करेगा कि क्या HashSet सेट 2 के तत्वों में से कोई है [ ] हो गया। यह गलत है, इसका मतलब है कि सेट 1 [] और सेट 2 [] में एक सामान्य तत्व है। इस प्रकार ये सेट से निराश नहीं होते हैं और झूठे होते हैं।

आइए हम यहां एक उदाहरण पर विचार करें, हम दो सेट लेंगे और उस पर हमारे एल्गोरिथ्म का प्रदर्शन करेंगे:

सेट 1 [] = {2, 1, 6, 9, 7}

सेट 2 [] = {4, 2, 19, 3}

हैशसेट मायसेट;

सेट 1 के मान को हैशसेट में संग्रहीत करने के लिए, हम set1 के प्रत्येक तत्व को पीछे छोड़ देंगे और सभी तत्वों को "myset" में सम्मिलित करेंगे।

सेट 1 के लिए []

i = 0, myset = {2}

i = 1, myset = {2, 1}

i = 2, myset = {2, 1, 6}

i = 3, myset = {2, 1, 6, 9}

i = 4, myset = {2, 1, 6, 9, 7}

हमें अपना हैशसेट मिला। हम HashSet में set2 [] (यदि कोई हो) के एक तत्व को खोजने के लिए तत्पर होंगे। सेट 2 ट्रेस करना [] = {4, 2, 19, 3};

j = 0, set2 [j] = 4

myset को HashSet में 4 नहीं मिलेंगे

j = 0, set2 [j] = 2

मायसेट हशसेट में 2 मिलेंगे, इसलिए यह गलत हो जाएगा और हमारे आउटपुट प्रिंट "ये डिस्जॉइंट सेट नहीं हैं"। यदि कोई भी अगर set2 [] के किसी भी तत्व को myset में मेल नहीं खाता है तो यह लूप से बाहर आ जाएगा और सही वापस आ जाएगा।

C ++ कोड यह जांचने के लिए कि क्या दो सेट असंतुष्ट हैं

#include<set>
#include<iostream>

using namespace std;

bool areDisjointSets(int set1[], int set2[],int n1,int n2)
{
    set<int> myset;

    for (int i = 0; i < n1; i++)
    {
        myset.insert(set1[i]);
    }
    for (int j = 0; j < n2; j++)
    {
        if (myset.find(set2[j]) != myset.end())
            return false;
    }
    return true;
}
int main()
{
    int set1[] = {1, 15, 8, 9, 6};
    int set2[] = {2, 4, 19, 3};

    int n1 = sizeof(set1) / sizeof(set1[0]);
    int n2 = sizeof(set2) / sizeof(set2[0]);

    if (areDisjointSets(set1, set2, n1, n2))
        cout << "These are Disjoint Sets";
    else
        cout << "These are not Disjoint Sets";

    return 0;
}
These are Disjoint Sets

जावा कोड यह जांचने के लिए कि क्या दो सेट असंतुष्ट हैं

import java.util.*;

class twoDisjointSets
{
    public static boolean areDisjointSets(int set1[], int set2[])
    {
        HashSet<Integer> myset = new HashSet<>();
        for (int i=0; i<set1.length; i++)
        {
            myset.add(set1[i]);
        }
        for (int j=0; j<set2.length; j++)
        {
            if (myset.contains(set2[j]))
            {
                return false;
            }
        }
        return true;
    }
    public static void main (String[] args)
    {
        int inputSet1[] = {1, 15, 8, 9, 6};
        int inputSet2[] = {2, 4, 19, 3};
        if (areDisjointSets(inputSet1, inputSet2))
            System.out.println("These are Disjoint Sets");
        else
            System.out.println("These are not Disjoint Sets");
    }
}
These are Disjoint Sets

जटिलता विश्लेषण

समय जटिलता

ओ (एम + एन) जहां "एम" और "N" क्रमशः सेट 1 और सेट 2 में तत्वों की संख्या है। सबसे पहले, हम पहले सेट के सभी तत्वों को हैशसेट में दर्ज करते हैं जो O (N) समय की जटिलता के लिए योगदान देता है। फिर हम दूसरे सेट के तत्वों को पीछे छोड़ते हैं।

अंतरिक्ष जटिलता

हे (एम) जहां "एम"  पहले सेट का आकार है। हम सरणी को संग्रहीत करने के लिए समाधान का अनुकूलन भी कर सकते हैं जिसमें तत्वों की न्यूनतम संख्या होती है।