Како да проверите дали два дадени комплети се неповрзани?


Ниво на тешкотија Лесно
Често прашувано во Факти Крстоносните Кулиза Нагаро Опера Snapdeal
Низа Бинарно пребарување Хаш Ларсен и Тубро Пребарување Сортирање

Проблемот „Како да провериме дали два дадени комплети се неповрзани?“ наведува дека претпоставуваме дека ви се дадени две множества во форма на низа, кажи множество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. Прогласи а HashSet.
  2. Вметнете ги сите елементи на множеството1 во HashSet.
  3. Поминајте ги сите елементи на множеството 2 [] и проверете дали HashSet содржи некој од елементите на множеството 2 [].
    1. Ако содржи, тогаш се враќа неточно.
  4. Врати се вистинито.

Објаснување

Дадовме изјава за проблем со која се бара да откриеме дали двата дадени множества се разделени множества или не. Двата комплети се претставени како низа. Useе користиме HashSet и ќе ги наследиме својствата на HashSet. HashSet не дозволува зачувување на дупликати вредности.

Прогласи а  Булова функција која едноставно враќа или точно или неточно. Passе пренесеме две низи на таа Булова функција и првото нешто што ќе стори е да ја зачува вредноста на множеството1 [] во HashSet и откако ќе ја зачува секоја вредност во неа на множеството1 [] ќе провери дали HashSet содржи некој од елементите на множеството 2 [ ] Враќа лажно, тоа значи дека множеството1 [] и множеството2 [] имаат заеднички елемент. Така, овие не се одвојувани множества и се враќаат лажни.

Ајде да разгледаме еден пример овде, ќе земеме два множества и ќе го извршиме нашиот алгоритам:

Сет1 [] = {2, 1, 6, 9, 7}

Сет2 [] = {4, 2, 19, 3}

HashSet myset;

За складирање на вредноста на множеството1 во HashSet, ќе го поминеме секој од елементите на множеството1 и ќе ги вметнеме сите елементи во „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}

Го добивме нашиот Хашсет. Со нетрпение очекуваме да најдеме елемент од множеството 2 [] (доколку го има) во HashSet. Преминување на множеството2 [] = {4, 2, 19, 3};

j = 0, множество2 [j] = 4

myset нема да најде 4 во HashSet

j = 0, множество2 [j] = 2

мисет ќе најде 2 во HashSet, па затоа ќе врати невистинити и нашите излезни отпечатоци „Овие не се раздвојни комплети“. Во случај доколку има кој било од елементите на множеството 2 [] не се совпаѓа во мојот состав, тој ќе излезе од јамката и ќе се врати точно.

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

Анализа на сложеност

Временска комплексност

О (м + н) каде "M" „Н“ се бројот на елементи соодветно во множеството1 и множеството2. Прво, ги внесуваме сите елементи од првиот сет во HashSet што придонесува за O (N) сложеност на времето. Потоа ги минуваме елементите на вториот сет.

Комплексноста на просторот

О (м) каде "M"  е големината на првиот сет. Ние исто така можеме да го оптимизираме решението за складирање на низата која има минимален број елементи.