கொடுக்கப்பட்ட இரண்டு செட் ஒத்திசைவில்லையா என்பதை எவ்வாறு சரிபார்க்கலாம்?


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது உண்மை உயர்வு குலிசா நாகரோ வேலை Snapdeal
அணி பைனரி தேடல் ஹாஷ் லார்சன் & டூப்ரோ தேடி வரிசையாக்க

சிக்கல் “கொடுக்கப்பட்ட இரண்டு தொகுப்புகள் முரண்பாடாக இருந்தால் எவ்வாறு சரிபார்க்க வேண்டும்?” வரிசை வடிவத்தில் உங்களுக்கு இரண்டு தொகுப்புகள் வழங்கப்பட்டுள்ளன என்று வைத்துக் கொள்ளுங்கள் 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. ஒரு அறிவிக்கவும் ஹாஷ்செட்.
  2. செட் 1 இன் அனைத்து கூறுகளையும் ஹாஷ்செட்டில் செருகவும்.
  3. செட் 2 [] இன் அனைத்து உறுப்புகளையும் கடந்து, ஹாஷ்செட் செட் 2 இன் எந்த உறுப்புகளையும் கொண்டிருக்கிறதா என்று சோதிக்கவும்.
    1. அது இருந்தால், தவறானது.
  4. உண்மைக்குத் திரும்பு.

விளக்கம்

கொடுக்கப்பட்ட இரண்டு செட் டிஜாயிண்ட் செட் இல்லையா என்பதைக் கண்டறிய ஒரு சிக்கல் அறிக்கையை நாங்கள் வழங்கியுள்ளோம். இரண்டு தொகுப்புகளும் ஒரு வரிசையாகக் குறிப்பிடப்படுகின்றன. நாங்கள் ஒரு ஹேஷ்செட்டைப் பயன்படுத்துவோம், மேலும் ஹாஷ்செட்டின் பண்புகளைப் பெறுவோம். நகல் மதிப்புகளை சேமிக்க ஒரு ஹாஷ்செட் அனுமதிக்காது.

ஒரு அறிவிக்கவும்  பூலியன் உண்மை அல்லது பொய்யை வழங்கும் செயல்பாடு. அந்த பூலியன் செயல்பாட்டிற்கு நாங்கள் இரண்டு வரிசைகளை அனுப்புவோம், அது முதலில் செய்ய வேண்டியது செட் 1 [] இன் மதிப்பை ஹாஷ்செட்டில் சேமிப்பதும், செட் 1 இன் ஒவ்வொரு மதிப்பையும் சேமித்து வைத்ததும் [] இது ஹாஷ்செட்டில் செட் 2 இன் ஏதேனும் கூறுகள் உள்ளதா என்பதை சரிபார்க்கும் [ ]. இது பொய்யைத் தருகிறது, அதாவது செட் 1 [] மற்றும் செட் 2 [] ஆகியவற்றுக்கு பொதுவான உறுப்பு உள்ளது. ஆகவே இவை ஒத்திசைவு தொகுப்புகள் அல்ல, தவறானவை.

இங்கே ஒரு உதாரணத்தைக் கருத்தில் கொள்வோம், நாங்கள் இரண்டு தொகுப்புகளை எடுத்து அதில் எங்கள் வழிமுறையைச் செய்வோம்:

அமை 1 [] = {2, 1, 6, 9, 7}

செட் 2 [] = {4, 2, 19, 3}

ஹாஷ்செட் மைசெட்;

செட் 1 இன் மதிப்பை ஹாஷ்செட்டில் சேமிப்பதற்காக, செட் 1 இன் ஒவ்வொரு உறுப்புகளையும் கடந்து, அனைத்து உறுப்புகளையும் “மைசெட்” இல் செருகுவோம்.

செட் 1 க்கு []

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

மைசெட் ஹாஷ்செட்டில் 4 ஐக் கண்டுபிடிக்க முடியாது

j = 0, set2 [j] = 2

myset ஹாஷ்செட்டில் 2 ஐக் கண்டுபிடிக்கும், எனவே இது தவறானது மற்றும் எங்கள் வெளியீடு அச்சிடுகிறது “இவை டிஜாயிண்ட் செட் அல்ல”. செட் 2 [] இன் உறுப்புகள் ஏதேனும் மைசெட்டில் பொருந்தவில்லை என்றால், அது சுழற்சியிலிருந்து வெளியே வந்து உண்மைக்குத் திரும்பும்.

சி ++ குறியீடு இரண்டு செட் ஒத்திசைந்ததா என்பதை சரிபார்க்க

#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 இல் உள்ள உறுப்புகளின் எண்ணிக்கை. முதலில், முதல் தொகுப்பின் அனைத்து கூறுகளையும் ஹாஷ்செட்டில் உள்ளிடுகிறோம், இது ஓ (என்) நேர சிக்கலுக்கு பங்களிக்கிறது. இரண்டாவது தொகுப்பின் கூறுகளை நாம் பயணிக்கிறோம்.

விண்வெளி சிக்கலானது

ஓ (மீ) எங்கே "மீ"  முதல் தொகுப்பின் அளவு. குறைந்தபட்ச எண்ணிக்கையிலான கூறுகளைக் கொண்ட வரிசையை சேமிப்பதற்கான தீர்வையும் மேம்படுத்தலாம்.