Како проверити да ли су два дата скупа дисјунктна?  


Ниво тешкоће Лако
Често питани у Фацтсет Пешачење Кулиза Нагарро радити Снапдеал
Ред Бинарна претрага Хасх Ларсен и Тоубро Претраживање сортирање

Проблем „Како проверити да ли су два дата скупа дисјунктна?“ стања која претпостављају да су вам дата два скупа у облику низа рец сет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. Пређите све елементе сет2 [] и проверите да ли ХасхСет садржи неки од елемената сет2 [].
    1. Ако садржи, онда враћа фалсе.
  4. Повратак истинит.

Објашњење

Дали смо изјаву о проблему која тражи да се утврди да ли су два дата скупа дисјунктни скупови или не. Оба скупа су представљена као низ. Користићемо ХасхСет и наследити својства ХасхСет-а. ХасхСет не дозвољава чување дуплираних вредности.

Изјавите а  Боолеан функција која једноставно враћа тачно или нетачно. Проследићемо два низа тој логичкој функцији и прво што ће урадити је чување вредности сет1 [] у ХасхСету и након складиштења сваке вредности у њему сет1 [] провериће да ли ХасхСет садржи неки од елемената сет2 [ ]. Враћа фалсе, што значи да сет1 [] и сет2 [] имају заједнички елемент. Дакле, ово нису раздвојени скупови и враћа фалсе.

Види такође
3Сум Леетцоде Солутион

Размотримо овде пример, узећемо два скупа и извршити свој алгоритам на њему:

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

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

ХасхСет мисет;

За чување вредности скупа1 у ХасхСету, прећи ћемо сваки од елемената скупа1 и уметнути све елементе у “мисет”.

За сет1 []

и = 0, мој скуп = {2}

и = 1, мисет = {2, 1}

и = 2, мисет = {2, 1, 6}

и = 3, мисет = {2, 1, 6, 9}

и = 4, мисет = {2, 1, 6, 9, 7}

Добили смо свој Хасхсет. Радоваћемо се проналажењу елемента сет2 [] (ако постоји) у ХасхСет-у. Прелазак скупа2 [] = {4, 2, 19, 3};

ј = 0, сет2 [ј] = 4

мисет неће наћи 4 у ХасхСет-у

ј = 0, сет2 [ј] = 2

мисет наћи ће 2 у ХасхСету, тако да ће вратити фалсе и наш излаз ће исписати „Ово нису дисјонтни скупови“. У случају да се било који од елемената сет2 [] не подудара у мисет-у, он ће изаћи из петље и вратити труе.

Ц ++ код за проверу да ли су два скупа неповезана  

#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

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

Сложеност времена

О (м + н) где "М" „Н“ су број елемената у скупу1 односно скупу2. Прво, у ХасхСет уносимо све елементе првог скупа што доприноси сложености времена О (Н). Затим прелазимо преко елемената другог скупа.

Види такође
Разврстајте целобројне бројеве по броју 1-битног решења са кодом

Сложеност простора

О (м) где "М"  је величина првог скупа. Такође можемо оптимизовати решење за чување низа који има минималан број елемената.