כיצד לבדוק אם שתי קבוצות נתונות אינן מחוברות?


רמת קושי קַל
נשאל לעתים קרובות סט עובדות טיול קוליזה נגארו לפעול Snapdeal
מערך חיפוש בינארי בליל לארסן וטוברו חיפוש מִיוּן

הבעיה "כיצד לבדוק אם שתי קבוצות נתונות אינן מחוברות?" קובע כי נניח שקיבלת שתי קבוצות בצורה של מערך נגיד set1 [] ו- set2 []. המשימה שלך היא לברר אם שתי הערכות הן ערכות Disjoint או לא.

דוגמה

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. הכריז א HashSet.
  2. הכנס את כל האלמנטים של set1 ל- HashSet.
  3. חצו את כל האלמנטים של set2 [] ובדקו אם HashSet מכיל את אחד האלמנטים של set2 [].
    1. אם הוא מכיל, מחזיר שקר.
  4. תחזיר נכון.

הסבר

נתנו הצהרת בעיה המבקשת לברר האם שתי הסטים הנתונים הם סטים לא צמודים או לא. שתי הערכות מיוצגות כמערך. נשתמש ב- HashSet וננחל את המאפיינים של HashSet. HashSet אינו מאפשר לאחסן ערכים כפולים.

הכריז א  בוליאני פונקציה אשר פשוט מחזירה נכון או לא נכון. נעביר שני מערכים לאותה פונקציה בוליאנית והדבר הראשון שהיא תעשה הוא לאחסן את הערך של set1 [] ל- HashSet ולאחר אחסון של כל ערך בו של set1 [] הוא יבדוק אם HashSet מכיל אלמנטים של set2 [ ]. זה מחזיר שקר, כלומר ל- set1 [] ו- set2 [] יש אלמנט משותף. לפיכך אלה אינם סטים ומחוברים כוזבים.

הבה נבחן דוגמה כאן, ניקח שתי קבוצות ונבצע עליה את האלגוריתם שלנו:

סט 1 [] = {2, 1, 6, 9, 7}

Set2 [] = {4, 2, 19, 3}

מכשיר HashSet;

לאחסון הערך של set1 ב- HashSet, נחצה כל אחד מהאלמנטים של set1 ונכניס את כל האלמנטים ל"מייס ".

לסט 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 [] (אם קיים) ב- HashSet. חוצה את set2 [] = {4, 2, 19, 3};

j = 0, set2 [j] = 4

myset לא ימצא 4 ב- HashSet

j = 0, set2 [j] = 2

myset ימצא 2 ב- HashSet, כך שהוא יחזיר שקר והפלט שלנו מדפיס "אלה לא סטים נפרדים". במקרה שאם אחד מהאלמנטים של set2 [] אינו תואם ב- myset, הוא ייצא מהלולאה ויחזיר true.

קוד 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

קוד Java כדי לבדוק אם שתי קבוצות אינן מחוברות

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

ניתוח מורכבות

מורכבות זמן

O (m + n) איפה "M" ו "N" הם מספר האלמנטים ב- set1 ו- set2 בהתאמה. ראשית, אנו מזינים את כל האלמנטים של הסט הראשון ל- HashSet התורם למורכבות הזמן O (N). ואז אנו חוצים את יסודות הסט השני.

מורכבות בחלל

O (m) איפה "M"  הוא גודל הסט הראשון. אנחנו יכולים גם לייעל את הפתרון לאחסון המערך שיש בו מספר מינימלי של אלמנטים.