Як праверыць, калі два дадзеныя наборы не перасякаюцца?


Узровень складанасці Лёгка
Часта пытаюцца ў Факты Паход Куліза Нагара Опера Snapdeal
масіў Двайковы пошук гашыш Larsen & Toubro Пошук сартаванне

Праблема "Як праверыць, калі два дадзеныя наборы не перасякаюцца?" дзяржавы, якія мяркуюць, што вам дадзены два наборы ў выглядзе масіва, скажам set1 [] і set2 []. Ваша задача - даведацца, з'яўляюцца гэтыя два наборы несумяшчальнымі наборамі.

Прыклад

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. Калі ён утрымлівае, вяртае false.
  4. Вярнуцца праўдай.

Тлумачэнне

Мы далі заяву пра праблему, якая просіць высветліць, з’яўляюцца два дадзеныя мноствы несумяшчальнымі мноствамі. Абодва наборы прадстаўлены ў выглядзе масіва. Мы будзем выкарыстоўваць HashSet і наследаваць ўласцівасці HashSet. HashSet не дазваляе захоўваць паўтараюцца значэнні.

Абвясціце а  Boolean функцыя, якая проста вяртае праўдзівае альбо ілжывае. Мы перададзім два масівы гэтай лагічнай функцыі, і першае, што яна зробіць, гэта захаванне значэння set1 [] у HashSet і пасля захоўвання ў ім кожнага значэння set1 [] ён праверыць, ці ўтрымлівае HashSet які-небудзь з элементаў set2 [ ]. Ён вяртае false, гэта азначае, што set1 [] і set2 [] маюць агульны элемент. Такім чынам, гэта не перасякальныя мноствы і вяртае false.

Давайце разгледзім прыклад тут, мы возьмем два наборы і выканаем на ім наш алгарытм:

Набор1 [] = {2, 1, 6, 9, 7}

Набор2 [] = {4, 2, 19, 3}

HashSet myset;

Для захоўвання значэння set1 у HashSet мы пройдзем кожны з элементаў 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}

Мы атрымалі свой хэшэт. Мы будзем рады знайсці элемент set2 [] (калі ён ёсць) у HashSet. Абход мноства2 [] = {4, 2, 19, 3};

j = 0, набор2 [j] = 4

myset не знойдзе 4 у HashSet

j = 0, набор2 [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) дзе «М» і "П" - колькасць элементаў у набор1 і набор2 адпаведна. Па-першае, мы ўводзім усе элементы першага набору ў HashSet, што спрыяе складанасці часу O (N). Тады мы пераходзім элементы другога набору.

Касмічная складанасць

O (м) дзе «М»  гэта памер першага набору. Мы таксама можам аптымізаваць рашэнне для захоўвання масіва, які мае мінімальную колькасць элементаў.