ಕೊಟ್ಟಿರುವ ಎರಡು ಸೆಟ್‌ಗಳು ಅಸಮಂಜಸವಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುವುದು ಹೇಗೆ?


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಫ್ಯಾಕ್ಟ್‌ಸೆಟ್ ಪಾದಯಾತ್ರೆ ಕುಲಿಜಾ ನಾಗರೋ ಒಪೆರಾ ಸ್ನ್ಯಾಪ್ಡಿಯಲ್
ಅರೇ ಬೈನರಿ ಹುಡುಕಾಟ ಹ್ಯಾಶ್ ಲಾರ್ಸೆನ್ ಮತ್ತು ಟೌಬ್ರೊ ಹುಡುಕಲಾಗುತ್ತಿದೆ ವಿಂಗಡಿಸಲಾಗುತ್ತಿದೆ

ಸಮಸ್ಯೆ “ಕೊಟ್ಟಿರುವ ಎರಡು ಸೆಟ್‌ಗಳು ಅಸಮಂಜಸವಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುವುದು ಹೇಗೆ?” ರಚನೆಯ ರೂಪದಲ್ಲಿ ನಿಮಗೆ ಎರಡು ಸೆಟ್‌ಗಳನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಭಾವಿಸೋಣ 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, ಮೈಸೆಟ್ = {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, ಸೆಟ್ 2 [ಜೆ] = 4

ಮೈಸೆಟ್ ಹ್ಯಾಶ್‌ಸೆಟ್‌ನಲ್ಲಿ 4 ಅನ್ನು ಕಂಡುಹಿಡಿಯುವುದಿಲ್ಲ

j = 0, ಸೆಟ್ 2 [ಜೆ] = 2

ಮೈಸೆಟ್ ಹ್ಯಾಶ್‌ಸೆಟ್‌ನಲ್ಲಿ 2 ಅನ್ನು ಕಾಣಬಹುದು, ಆದ್ದರಿಂದ ಅದು ಸುಳ್ಳನ್ನು ನೀಡುತ್ತದೆ ಮತ್ತು ನಮ್ಮ output ಟ್‌ಪುಟ್ “ಇವುಗಳು ಡಿಜಾಯಿಂಟ್ ಸೆಟ್‌ಗಳಲ್ಲ” ಎಂದು ಮುದ್ರಿಸುತ್ತದೆ. ಒಂದು ವೇಳೆ ಸೆಟ್ 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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಮೀ + ಎನ್) ಅಲ್ಲಿ "ಮೀ" ಮತ್ತು “ಎನ್” ಕ್ರಮವಾಗಿ ಸೆಟ್ 1 ಮತ್ತು ಸೆಟ್ 2 ನಲ್ಲಿನ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಮೊದಲಿಗೆ, ನಾವು ಮೊದಲ ಸೆಟ್‌ನ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಹ್ಯಾಶ್‌ಸೆಟ್‌ಗೆ ನಮೂದಿಸುತ್ತೇವೆ ಅದು ಒ (ಎನ್) ಸಮಯದ ಸಂಕೀರ್ಣತೆಗೆ ಕೊಡುಗೆ ನೀಡುತ್ತದೆ. ನಂತರ ನಾವು ಎರಡನೇ ಗುಂಪಿನ ಅಂಶಗಳನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಮೀ) ಅಲ್ಲಿ "ಮೀ"  ಇದು ಮೊದಲ ಗುಂಪಿನ ಗಾತ್ರವಾಗಿದೆ. ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಅಂಶಗಳನ್ನು ಹೊಂದಿರುವ ರಚನೆಯನ್ನು ಸಂಗ್ರಹಿಸಲು ನಾವು ಪರಿಹಾರವನ್ನು ಅತ್ಯುತ್ತಮವಾಗಿಸಬಹುದು.