ပေးထားသောအစုံနှစ်ခုမပြိုကွဲလျှင်မည်သို့စစ်ဆေးရမည်နည်း။


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အချက်အလက် ခရီးသွား Kuliza နာဂ တေးသံစုံကဇါတ် Snapdeal
အခင်းအကျင်း Binary Search ကို hash Larsen & Toubro ရှာဖွေခြင်း sorting

ပြgivenနာ“ ပေးထားသောအစုံနှစ်ခုသည်မချိတ်ဆက်နေမှုကိုမည်သို့စစ်ဆေးရမည်နည်း” သင်ခင်းကျင်း၏ပုံစံနှစ်ခုအစုံပေးထားကြသည်ဆိုပါစို့ set1 [] နှင့် set2 [] ဟုပြောသည်။ သင်၏တာဝန်မှာအစုံနှစ်ခုသည် Disjoint Sets ဟုတ်မဟုတ်ရှာဖွေရန်ဖြစ်သည်။

နမူနာ

inputSet1[] = {1, 15, 8, 9, 6}
inputSet2[] = {2, 4, 19, 3}
These are Disjoint Sets

ရှင်းလင်းချက်

အဘယ်သူမျှမဘုံဒြပ်စင်နှစ်ခုလုံးကို set မှာရှိပါတယ်ဒါကြောင့်သူတို့ disjoint အစုံဖြစ်ကြသည်

inputSet1[] = {2, 1, 6, 9, 7}
inputSet2[] = {2, 4, 19, 3}
These are not Disjoint Sets

ရှင်းလင်းချက်

ဒီနေရာမှာ 2 set ကိုနှစ် ဦး စလုံးအတွက်ဘုံဒြပ်စင်ဖြစ်ပါတယ်ဒါကြောင့်သူတို့ disjoint အစုံမရှိကြပေ။

algorithm

  1. a) ကြေညာပါ HashSet.
  2. set1 ၏ element အားလုံးကို HashSet ထဲသို့ထည့်ပါ။
  3. set2 [] ၏အစိတ်အပိုင်းအားလုံးကိုဖြတ်ပြီး HashSet တွင် set2 ၏ဒြပ်စင်တစ်ခုခုရှိမရှိစစ်ဆေးပါ။
    1. ၎င်းတွင်ပါ ၀ င်ပါက false ကိုပြန်ပို့သည်။
  4. ပြန်လာမှန်

ရှင်းလင်းချက်

ကျနော်တို့နှစ်ခုပေးထားသောအစုံ disjoint အစုံရှိမရှိသို့မဟုတ်မရှိမရှိထွက်ရှာရန်တောင်းတဲ့ပြproblemနာကြေညာချက်ပေးပြီ။ အစုံနှစ်ခုလုံးကိုခင်းကျင်းပြသထားတယ်။ ကျွန်ုပ်တို့သည် HashSet ကိုအသုံးပြုပြီး HashSet ၏ဂုဏ်သတ္တိများကိုအမွေခံရမည်။ HashSet သည်ထပ်တူတန်ဖိုးများကိုသိမ်းဆည်းရန်ခွင့်မပြုပါ။

a) ကြေညာပါ  boolean ရိုးရှင်းစွာစစ်မှန်တဲ့သို့မဟုတ်မှားယွင်းသောဖြစ်စေပြန်လာသော function ကို။ ၎င်း Boolean function သို့ arrays နှစ်ခုကိုသွားမည်။ ပထမတစ်ခုမှာ set1 ၏တန်ဖိုးကို HashSet သိုလှောင်ရန်ဖြစ်သည်။ ၎င်းတွင် set1 ၏တန်ဖိုးတစ်ခုစီကိုသိမ်းဆည်းပြီးနောက် HashSet တွင် set2 ၏မည်သည့်ဒြပ်စင်ပါမပါကိုစစ်ဆေးလိမ့်မည်။ ] ။ သူသည် false ကို return ပြန်သည်။ ဆိုလိုသည်မှာ set1 [] နှင့် set2 [] တွင်တူညီသောဒြပ်စင်ရှိသည်။ ထို့ကြောင့်ဤ disjoint အစုံမမှန်သောပြန်လာ။

ဒီမှာဥပမာတစ်ခုကိုလေ့လာကြည့်ရအောင်။ နှစ်စုံကိုယူပြီးငါတို့ရဲ့ algorithm ကိုလုပ်မယ်။

Set1 [] = {၂၊ ၁၊ ၆၊ ၉၊ ၇}

Set2 [] = {၄၊ ၂၊ ၁၉၊ ၃}

HashSet myset;

set1 ၏တန်ဖိုးကို HashSet ထဲသို့သိုလှောင်ရန်အတွက် set1 ၏ element တစ်ခုစီကိုဖြတ်ပြီး element အားလုံးကို "myset" ထဲသို့ထည့်ပါလိမ့်မည်။

set1 အတွက် []

i = 0, myset = {2}

i = 1, myset = {၂၊ ၁}

i = 2, myset = {2, 1, 6}

i = 3, myset = {2, 1, 6, 9}

i = 4, myset = {2, 1, 6, 9, 7}

ငါတို့ Hashset ရတယ် ကျွန်ုပ်တို့သည် HashSet တွင် set2 [] (ရှိခဲ့လျှင်) ၏ element တစ်ခုကိုရှာရန်မျှော်လင့်နေမည်။ အဆိုပါ set2 ဖြတ်သန်း [] = {4, 2, 19, 3};

ည = 0, set2 [ည] = 4

myset သည် HashSet တွင် 4 ကိုရှာမတွေ့ပါ

ည = 0, set2 [ည] = 2

ကဗျာ HashSet တွင် 2 ကိုတွေ့လိမ့်မည်, ဒါကြောင့် false ပြန်လာလိမ့်မည်နှင့်ငါတို့ output ကို "ဒီ Disjoint Sets မဟုတ်" print ထုတ် အကယ်၍ set2 [] မှမည်သည့်အချက်အလက်များမဆိုကျွန်ုပ်၏ myset နှင့်မကိုက်ညီပါက၎င်းသည် loop မှထွက်လာပြီး true ဖြစ်လာလိမ့်မည်။

နှစ်ခုအစုံ disjoint ဟုတ်မဟုတ်ကိုစစ်ဆေး 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

နှစ်ခုအစုံ disjoint ဟုတ်မဟုတ်စစ်ဆေးပါရန် Java code ကို

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (m + n) ဘယ်မှာ "m" နှင့် “ n” အသီးသီး set1 နှင့် set2 အတွက်ဒြပ်စင်များ၏အရေအတွက်ဖြစ်ကြသည်။ ပထမ ဦး စွာကျွန်ုပ်တို့သည်ပထမအစု၏ဒြပ်စင်အားလုံးကို H (H) အချိန်ရှုပ်ထွေးမှုအတွက်အထောက်အကူပြုသော HashSet သို့ထည့်ပါ။ ထိုအခါကျွန်ုပ်တို့သည်ဒုတိယ set ၏ဒြပ်စင်ကိုဖြတ်သန်း။

အာကာသရှုပ်ထွေးမှု

အို (မီတာ) ဘယ်မှာ "m"  ပထမ ဦး ဆုံးအစု၏အရွယ်အစားဖြစ်ပါတယ်။ ကျွန်ုပ်တို့သည်အနည်းဆုံးဒြပ်စင်အရေအတွက်ရှိသော array ကိုသိမ်းဆည်းရန်အဖြေကိုအကောင်းဆုံးပြုလုပ်နိုင်သည်။