Verilən iki dəstin ayrıldığını necə yoxlamaq olar?

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Məlumat dəsti Piyada çox yol qət eləmək Kuliza Nagarro Opera Snapdeal
Geyim İkili axtarış Sükut Larsen & Toubro Axtarış çeşidləyiciBaxılıb 38

Problem "Verilmiş iki dəstin ayrıldığını necə yoxlamaq olar?" deyirlər ki, sizə set1 [] və set2 [] dizisi şəklində iki dəst verilmişdir. Taskınız, iki dəstin Ayrılmış Dəstlər olub olmadığını öyrənməkdir.

Pin

misal

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

Izahat

Hər iki dəstdə ortaq element olmadığı üçün onlar bir-birindən ayrılmış çoxluqlardır

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

Izahat

Burada 2, hər iki dəstdə ortaq bir elementdir, beləliklə onlar ayrılmaz dəstlər deyillər.

Alqoritm

  1. Bəyan edin a HashSet.
  2. Set1-in bütün elementlərini HashSet-ə daxil edin.
  3. Set2 [] elementlərinin hamısını keçin və HashSet-də set2 [] elementlərindən hər hansı birinin olub olmadığını yoxlayın.
    1. Əgər ehtiva edirsə, yalnış qaytarır.
  4. Doğru qayıdın.

Izahat

Verilən iki dəstin ayrılmış çoxluq olub olmadığını öyrənməyi xahiş edən bir problem ifadəsi verdik. Hər iki dəst bir sıra kimi təmsil olunur. HashSet istifadə edəcəyik və HashSet xüsusiyyətlərini miras alacağıq. HashSet təkrarlanan dəyərləri saxlamağa icazə vermir.

Bəyan edin a  Boolean sadəcə doğru və ya yalnış qaytaran funksiya. Bu Boolean funksiyasına iki sıra ötürəcəyik və ilk edəcəyi şey set1 [] dəyərinin HashSet-ə saxlanılmasıdır və set1 [] içindəki hər bir dəyəri saxladıqdan sonra HashSet-də set2 [elementlərindən hər hansı birinin olub olmadığını yoxlayacaqdır. ]. Yanlış qaytarır, yəni set1 [] və set2 [] ortaq bir elementə sahibdir. Beləliklə, bunlar bir-birindən ayrılan dəstlər deyildir və false qaytarır.

Burada bir nümunəni nəzərdən keçirək, iki dəst götürəcəyik və bunun üzərində alqoritmimizi yerinə yetirəcəyik:

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

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

HashSet dəsti;

Set1 dəyərini HashSet-də saxlamaq üçün set1 elementlərinin hər birini keçib bütün elementlərini “myset” ə əlavə edəcəyik.

Set1 üçün []

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}

Haşetimizi aldıq. HashSet-də set2 [] elementi (varsa) tapmaq üçün səbirsizliklə gözləyəcəyik. Set2-dən keçmək [] = {4, 2, 19, 3};

j = 0, set2 [j] = 4

myset, HashSet-də 4 tapa bilməz

j = 0, set2 [j] = 2

myset HashSet-də 2-ni tapacaq, beləliklə false olaraq dönəcək və çıxdığımız “Bunlar Disjoint Setlər deyil”. Set2 [] elementlərindən hər hansı biri myset-ə uyğun gəlmirsə, döngədən çıxacaq və doğru qayıdacaqdır.

İki dəstin ayrıldığını yoxlamaq üçün C ++ kodu

#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

İki dəstin ayrıldığını yoxlamaq üçün Java kodu

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ürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (m + n) hara "M" "N" sırasıyla set1 və set2-dəki elementlərin sayıdır. Əvvəlcə ilk dəstin bütün elementlərini H (S) zaman mürəkkəbliyinə kömək edən HashSet-ə daxil edirik. Sonra ikinci dəstin elementlərini keçirik.

Kosmik Mürəkkəblik

O (m) hara "M"  ilk dəstin ölçüsüdür. Minimum element sayı olan massivi saxlamaq üçün həll variantını da optimallaşdırmaq olar.

Translate »