Берилген эки топтомдун бөлүнгөндүгүн кантип текшерсе болот?


Кыйынчылык деңгээли жеңил
Көп суралган Factset селсаяктоо Кулиза Нагарро опера Snapdeal
согуштук тизме Binary Search таштанды Ларсен & Toubro издөө сорттоо

Маселе "Берилген эки топтомдун айырмачылыктарын кантип текшерсе болот?" set1 [] жана set2 [] массив түрүндө сизге эки топтом берилген деп ойлойм. Сиздин милдетиңиз - эки топтомдун Disjoint Sets же жок экендигин билүү.

мисал

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 топтомдо кеңири тараган элемент, ошондуктан алар ажыратылбаган топтомдор эмес.

Algorithm

  1. Декларация a HashSet.
  2. Set1 бардык элементтерин HashSet ичине кыстарыңыз.
  3. Set2 [] элементтеринин бардыгын кыдырып, HashSetте set2 [] элементтеринин бирөөсүн камтыгандыгын текшерип чыгыңыз.
    1. Эгер анда камтылса, анда false дегенди кайтарат.
  4. Чындыкты кайтаруу.

түшүндүрүү

Берилген эки топтун бир-биринен ажыратылган же жок экендигин билүүнү суранган көйгөйлүү билдирүүнү бердик. Эки топтом тең массив катары берилген. Биз HashSet колдонуп, HashSet касиеттерин мураска алабыз. HashSet кайталанган баалуулуктарды сактоого жол бербейт.

Декларация a  Буль жөн гана чындыкты же жалганды кайтаруучу функция. Бул логикалык функцияга эки массивди өткөрүп беребиз жана ал биринчи жасай турган нерсе 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 [] элементтеринин бири 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) кайда "М" жана "N" set1 жана set2деги элементтердин саны. Биринчиден, биринчи топтомдун бардык элементтерин HashSetке киргизебиз, бул O (N) убакыттын татаалдыгына өбөлгө түзөт. Андан кийин экинчи топтомдун элементтерин аралайбыз.

Космостун татаалдыгы

O (м) кайда "М"  биринчи топтомдун көлөмү. Ошондой эле, элементтердин минималдуу саны бар массивди сактоо үчүн чечимди оптималдаштырсак болот.