Берілген екі жиынтықтың бөлінгендігін қалай тексеруге болады?


Күрделілік дәрежесі оңай
Жиі кіреді Деректер жинағы жорық Кулиза Нагарро опера Шапшаң
Array Екілік іздеу Hash Ларсен және Тубро іздеу Сұрыптау

«Берілген екі жиынтықтың біріктірілгендігін қалай тексеруге болады?» Мәселесі. сізге 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 жиынтығының кез-келген элементтерінің бар-жоғын тексеріңіз [].
    1. Егер ол бар болса, онда false мәнін қайтарады.
  4. Ақиқатқа оралу

Түсіндіру

Біз берілген екі жиынның ажыратылған жиынтыққа жататындығын немесе болмайтындығын анықтайтын проблемалық мәлімдеме бердік. Жиындардың екеуі де массив түрінде ұсынылған. Біз HashSet-ті қолданамыз және HashSet қасиеттерін мұраға аламыз. HashSet қайталанатын мәндерді сақтауға рұқсат бермейді.

Декларация а  Бульдік жай немесе жалған мәнін қайтаратын функция. Біз бұл логикалық функцияға екі массив жібереміз және ол біріншіден set1 [] мәнін HashSet-ке сақтайды және әрбір set1 [] ішіндегі әрбір мәнді сақтағаннан кейін HashSet-те set2 элементтерінің кез келгені бар-жоғын тексереді. ]. Ол «false» мәнін қайтарады, яғни set1 [] және set2 [] жалпы элементі болады. Осылайша, бұл бөлінбеген жиын емес және жалғанға қайтарады.

Осы жерде бір мысал қарастырайық, біз екі жиынтығын аламыз және ол бойынша алгоритмімізді орындаймыз:

Set1 [] = {2, 1, 6, 9, 7}

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

HashSet myset;

Set1 мәнін HashSet ішіне сақтау үшін set1 элементтерінің әрқайсысын айналып өтіп, барлық элементтерді «myset» ішіне енгіземіз.

Set1 үшін []

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 HashSet ішінде 4 таба алмайды

j = 0, set2 [j] = 2

myset HashSet ішінде 2-ні табады, сондықтан ол «false» мәнін қайтарады және біздің шығарылымымыз «Бұлар жиынтық жиынтықтар емес». Егер жиынтықта set2 [] элементтерінің кез-келгені сәйкес келмесе, онда ол циклден шығады және 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»  бірінші жиынтықтың өлшемі. Сонымен қатар, элементтердің минималды саны бар массивті сақтау үшін шешімді оңтайландыруға болады.