როგორ გადავამოწმოთ, ორი მოცემული სიმრავლე არის თუ არა ერთმანეთთან კავშირი?


Რთული ტური Easy
ხშირად ეკითხებიან ფაქტები ლაშქრობა კულიზა ნაგარო ოპერისა Snapdeal
Array ორობითი ძებნა Hash ლარსენი და ტუბრო Searching დახარისხება

პრობლემა „როგორ გადავამოწმოთ, ორი მოცემული ნაკრები არის თუ არა ერთმანეთისაგან გამიჯნული?“ აცხადებს, რომ დავუშვათ, რომ მასივის სახით მოგეცათ ორი ნაკრები, მაგალითად set1 [] და 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. გამოაცხადეთ ა HashSet.
  2. ჩასვით HashSet– ის ნაკრების ყველა ელემენტი.
  3. გადახედეთ set2 [] - ის ყველა ელემენტს და შეამოწმეთ, შეიცავს თუ არა HashSet set2– ის რომელიმე ელემენტს.
    1. თუ ის შეიცავს, მაშინ ყალბი აბრუნებს.
  4. ნამდვილი დაბრუნება

განმარტება

ჩვენ მივეცით პრობლემის დებულებას, რომელიც ითხოვს გაარკვიოს, მოცემული ორი სიმრავლე არის თუ არა ცალკეული სიმრავლე. ორივე ნაკრები წარმოდგენილია მასივის სახით. ჩვენ გამოვიყენებთ HashSet- ს და დავიმკვიდრებთ HashSet- ის თვისებებს. HashSet არ იძლევა დუბლირებული მნიშვნელობების შენახვის საშუალებას.

გამოაცხადეთ ა  ლოგიკური ფუნქცია, რომელიც აბრუნებს ან ჭეშმარიტს ან არასწორს. ჩვენ გადავცემთ ორ მასივს ამ ლოგიკურ ფუნქციას და პირველი, რაც ის გააკეთებს არის set1 [] მნიშვნელობის შენახვა HashSet- ში და set1- ის მასში თითოეული მნიშვნელობის შენახვის შემდეგ [] ის შეამოწმებს შეიცავს თუ არა HashSet set2- ის რომელიმე ელემენტს. ]. იგი ცრუობს, ეს ნიშნავს, რომ set1 [] და set2 [] აქვთ საერთო ელემენტი. ამრიგად, ეს არ არის შეუცვლელი ნაკრები და არასწორია.

მოდით განვიხილოთ მაგალითი აქ, ჩვენ ავიღებთ ორ სიმრავლეს და შევასრულებთ მასზე ჩვენს ალგორითმს:

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

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

HashSet myset;

Set1- ის მნიშვნელობის შესანახად HashSet- ში, ჩვენ გადავხედავთ set1- ის თითოეულ ელემენტს და ჩავამატებთ ყველა ელემენტს "myset" - ში.

კომპლექტისთვის 1 []

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 [] ელემენტის ელემენტი (ასეთის არსებობის შემთხვევაში). კომპლექტის გავლა 2 [] = {4, 2, 19, 3};

j = 0, კომპლექტი 2 [j] = 4

myset ვერ იპოვის 4-ს HashSet- ში

j = 0, კომპლექტი 2 [j] = 2

ჩასვლა იპოვის 2-ს HashSet- ში, ასე რომ, ის დააბრუნებს ყალბი და ჩვენს გამომავალ ბეჭდავს "ეს არ არის ცალკეული ნაკრები". იმ შემთხვევაში, თუ არსებობს, თუ 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

ჯავის კოდი, რათა შეამოწმოს არის თუ არა ორი ნაკრები ერთმანეთისაგან განსხვავებული

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 (მ + ნ) სადაც "მ" და "ნ" შესაბამისად, ელემენტთა რაოდენობაა set1 და set2 შესაბამისად. პირველი, HashSet– ში შევიტანთ პირველი ნაკრების ყველა ელემენტს, რაც ხელს უწყობს O (N) დროის სირთულეს. შემდეგ ჩვენ გადავკვეთთ მეორე ნაკრების ელემენტებს.

სივრცის სირთულე

ო (მ) სადაც "მ"  არის პირველი ნაკრების ზომა. ასევე, შეგვიძლია გამოვყოთ მასივის შესანახად გამოსავალი, რომელსაც აქვს ელემენტების მინიმალური რაოდენობა.