څنګه وټاکئ چې دوه ورکړل شوي سیټونه ناڅاپي دي؟


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي حقیقت هیک کولیزا نګارو اوپرا سنیپډیل
پیشه دوه لمبري پلټنه هاش لارسن او توابرو لټون کول ترتیب کول

ستونزه "د دې څرنګوالی څرنګوالی چې دوه ورکړل شوي سیټونه سره جلا کیږي که نه؟" په ګوته کوي چې فرض کړئ چې تاسو ته د سیر سیټ 1 [] او 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. اعلامیه a هش سیټ.
  2. په هټ سیټ کې د سیټ 1 ټول عناصر دننه کړئ.
  3. د سیټ 2 ټول عناصر وټاکئ [] او چیک کړئ چې ایا هش سیټ د سیټ 2 [] عناصرو څخه لري.
    1. که دا پکې وي ، نو غلط راګرځي.
  4. ریښتیا راستنیدل.

تشریح

موږ د ستونزې بیان درکړو چې پوښتنه یې ترې وکړه چې ایا دوه ورکړل شوي سیټونه ناڅرګند سیټونه دي که نه. دواړه سیټونه د یو صف په توګه ښودل شوي. موږ به د هش شاټ وکاروو او د هش سیټ ملکیتونه به وراثت کړو. یو هش سیټ اجازه نه ورکوي د نقل ارزښتونه ذخیره کړي.

اعلامیه a  بولین هغه فعالیت چې په ساده ډول ریښتیني کیږي یا غلط. موږ به د بولان فعالیت ته دوه تیرونه واړوو او لومړی کار به یې د سیټ 1 [] ارزښت هش سیټ ته وسپاري او وروسته د هر قیمت ذخیره کولو وروسته [دا] سیټ به وګوري چې ایا هش شیټ د سیټ 1 عناصرو څخه لري [ ]. دا غلط راستنوي ، پدې معنی چې سیټ 2 [] او سیټ 1 [] یو عام عنصر لري. پدې توګه دا ناخالص سیټونه ندي او غلط راګرځي.

راځئ چې دلته یو مثال په پام کې ونیسو ، موږ به دوه سیټونه واخلو او پدې باندې به زموږ الګوریتم ترسره کړو:

سیټ 1 [] = {2 ، 1 ، 6 ، 9 ، 7}

سیټ 2 [] = {4 ، 2 ، 19 ، 3

د هش سیټ میسیټ؛

په هش سیټ کې د set1 ارزښت ذخیره کولو لپاره ، موږ به د set1 هر عنصر تیر کړو او ټول عناصر به "Myset" کې داخل کړو.

د set1 لپاره []

i = 0 ، Myset = {2}

i = 1 ، میسیټ = {2 ، 1}

i = 2 ، میسیټ = {2 ، 1 ، 6}

i = 3 ، میسیټ = {2 ، 1 ، 6 ، 9}

i = 4 ، میسیټ = {2 ، 1 ، 6 ، 9 ، 7}

موږ خپل هشیتټ ترلاسه کړ. موږ به په هاشسیټ کې د سیټ 2 [] (که کوم یو) عنصر موندلو ته سترګې په لار یو. د سیټ 2 تعقیب کول [] = {4 ، 2 ، 19 ، 3}؛

j = 0 ، set2 [j] = 4

myset به په هشسیټ کې 4 ونه موندل شي

j = 0 ، set2 [j] = 2

Myset په هشسیټ کې به 2 ومومئ ، نو دا به غلط او زموږ د محصول پرنټونه "دا د ناڅرګند کولو سیټونه ندي". په هغه صورت کې که کوم یو د سیټ 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

د پیچلتیا تحلیل

د وخت پیچلتیا

O (m + n) هلته "م" او "n" په ترتیب سره په set1 او set2 کې د عناصرو شمیر دي. لومړی ، موږ په هش سیټ کې د لومړي سیټ ټول عناصر داخل کوو کوم چې د O (N) وخت پیچلتیا لپاره برخه اخلي. بیا موږ د دوهم سیټ عناصر تیروو.

د ځای پیچلتیا

O (م) هلته "م"  د لومړۍ سیټ اندازه ده. موږ کولی شو د صفاتو ذخیره کولو لپاره حل غوره کړو کوم چې لږترلږه عناصر لري.