Өгөгдсөн хоёр багц задарсан эсэхийг хэрхэн шалгах вэ?


Хэцүү байдлын түвшин Easy
Байнга асуудаг Factset явган аялал Кулиза Нагарро Opera Snapdeal
Array Хоёртын хайлт Хаш Ларсен ба Тубро хайх Ангилах

Асуудал "Өгөгдсөн хоёр багц задарсан эсэхийг хэрхэн шалгах вэ?" 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 нь олонлогийн хоёуланд нь байдаг нийтлэг элемент тул тэдгээр нь салангид багц биш юм.

Алгоритм

  1. Мэдүүлэх a HashSet.
  2. Set1-ийн бүх элементүүдийг HashSet дээр оруулна уу.
  3. Set2 [] бүх элементүүдийг туулж, HashSet нь set2 [] элементүүдийн аль нэгийг агуулсан эсэхийг шалгана уу.
    1. Хэрэв агуулсан бол худал гэсэн утгыг буцаана.
  4. Буцах үнэн.

Тайлбар

Өгөгдсөн хоёр багц нь задарсан олонлогууд мөн үү үгүй ​​юу гэдгийг олж мэдэхийг хүссэн асуудлын хариуг өгсөн. Энэ хоёр багцыг массив хэлбэрээр илэрхийлдэг. Бид HashSet ашиглаж, HashSet-ийн шинж чанарыг өвлөх болно. HashSet нь давхардсан утгыг хадгалахыг зөвшөөрдөггүй.

Мэдүүлэх a  Boolean үнэн эсвэл худлыг буцааж өгдөг функц. Энэ Boolean функцэд бид хоёр массив дамжуулах бөгөөд хамгийн түрүүнд хийх зүйл бол set1 [] утгыг HashSet-д хадгалах бөгөөд утга тус бүр дэх set1 [] дотор хадгалагдсаны дараа HashSet нь set2-ийн аль нэг элемент агуулсан эсэхийг шалгах болно. ]. Энэ нь худал утгыг буцаана, энэ нь 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 дээрээс олохыг бид тэсэн ядан хүлээх болно. Сет2-ээр дайран өнгөрөх [] = {4, 2, 19, 3};

j = 0, set2 [j] = 4

myset нь HashSet дээр 4-ийг олохгүй

j = 0, set2 [j] = 2

myset нь HashSet дээр 2-ийг олох тул худал утгыг буцаах бөгөөд бидний гаралт "Эдгээр нь салангид багц биш юм" хэвлэнэ. Хэрэв set2 [] элементийн аль нэг нь myset-тэй таарахгүй байвал энэ нь давталтаас гарч үнэн болно.

Хоёр багц задарсан эсэхийг шалгах 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 (м) хаана "М"  нь эхний багцын хэмжээ юм. Бид хамгийн бага тооны элемент бүхий массивыг хадгалах шийдлийг оновчтой болгож чадна.