ວິທີການກວດສອບຖ້າສອງຊຸດທີ່ຖືກມອບໃຫ້ຖືກກຽດຊັງ?


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ປັດໃຈ hike ກຸລະກິ ນາກາໂຣ Opera Snapdeal
Array ການຄົ້ນຫາຖານສອງ Hash Larsen & Toubro ຊອກຫາ ຮຽງລໍາດັບ

ປັນຫາ“ ວິທີການກວດສອບຖ້າສອງຊຸດຖືກຍົກເລີກ?” ລະບຸວ່າເຈົ້າຄິດວ່າເຈົ້າໄດ້ຮັບສອງຊຸດໃນຮູບແບບຂບວນກ່າວວ່າ 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. ປະກາດກ HashSet.
  2. ໃສ່ທຸກອົງປະກອບຂອງ set1 ລົງໃນ HashSet.
  3. ລອກເອົາທຸກໆອົງປະກອບຂອງ set2 [] ແລະກວດເບິ່ງວ່າ HashSet ມີສ່ວນປະກອບໃດ ໜຶ່ງ ຂອງ set2 [].
    1. ຖ້າມັນບັນຈຸຢູ່, ຫຼັງຈາກນັ້ນກໍ່ສົ່ງຄືນ ຄຳ ປອມ.
  4. ກັບຄືນມາເປັນຄວາມຈິງ.

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ໃຫ້ ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາທີ່ຂໍໃຫ້ຄົ້ນພົບວ່າຊຸດທີ່ມອບໃຫ້ທັງສອງຊຸດແມ່ນຊຸດທີ່ ໜ້າ ກຽດຊັງຫລືບໍ່. ທັງສອງຊຸດແມ່ນເປັນຕົວແທນເປັນອາເລ. ພວກເຮົາຈະໃຊ້ HashSet ແລະສືບທອດຄຸນສົມບັດຂອງ HashSet. HashSet ບໍ່ອະນຸຍາດໃຫ້ເກັບຄ່າທີ່ຊ້ ຳ ກັນ.

ປະກາດກ  ບົວບານ ໜ້າ ທີ່ເຊິ່ງພຽງແຕ່ສົ່ງຄືນທັງຄວາມຈິງຫຼືຜິດ. ພວກເຮົາຈະສົ່ງອາຄານສອງຢ່າງໃຫ້ຟັງຊັນ Boolean ແລະສິ່ງ ທຳ ອິດທີ່ມັນຈະເຮັດແມ່ນເກັບຮັກສາຄ່າຂອງ set1 [] ໃຫ້ HashSet ແລະຫຼັງຈາກເກັບແຕ່ລະຄ່າຂອງມັນຢູ່ໃນ set1 [] ມັນຈະກວດເບິ່ງວ່າ HashSet ມີສ່ວນປະກອບໃດ ໜຶ່ງ ຂອງ set2 [ ]. ມັນກັບຄືນບໍ່ຖືກຕ້ອງ, ນັ້ນ ໝາຍ ຄວາມວ່າ set1 [] ແລະ set2 [] ມີສ່ວນປະກອບທົ່ວໄປ. ດັ່ງນັ້ນສິ່ງເຫລົ່ານີ້ບໍ່ແມ່ນຊຸດທີ່ຜິດຫວັງແລະສົ່ງຄືນບໍ່ຖືກຕ້ອງ.

ໃຫ້ພວກເຮົາພິຈາລະນາຕົວຢ່າງຢູ່ທີ່ນີ້, ພວກເຮົາຈະເອົາສອງຊຸດແລະປະຕິບັດລະບົບຂອງພວກເຮົາກ່ຽວກັບມັນ:

ຊຸດ 1 [] = {2, 1, 6, 9, 7}

ຊຸດ 2 [] = {4, 2, 19, 3}

mys HashSet;

ສຳ ລັບການຈັດເກັບຄ່າຂອງ 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 [] (ຖ້າມີ) ໃນ HashSet. ການ ກຳ ນົດຄ່າທີ່ ກຳ ນົດໄວ້ 2 [] = {4, 2, 19, 3};

j = 0, ຊຸດ 2 [j] = 4

myset ຈະບໍ່ພົບ 4 ໃນ HashSet

j = 0, ຊຸດ 2 [j] = 2

myset ຈະພົບເຫັນ 2 ໃນ HashSet, ສະນັ້ນມັນຈະສົ່ງຄືນຂໍ້ມູນທີ່ບໍ່ຖືກຕ້ອງແລະຜົນຜະລິດຂອງພວກເຮົາ“ ເຫຼົ່ານີ້ບໍ່ແມ່ນຊຸດທີ່ຜິດຫວັງ”. ໃນກໍລະນີຖ້າມີອົງປະກອບໃດ ໜຶ່ງ ຂອງ set2 [] ບໍ່ກົງກັບ myset ແລ້ວມັນກໍ່ຈະອອກມາຈາກວົງຈອນແລະກັບມາເປັນຄວາມຈິງ.

ລະຫັດ C ++ ເພື່ອກວດເບິ່ງວ່າມີສອງຊຸດຖືກ disjoint

#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 ເພື່ອກວດກາເບິ່ງວ່າມີສອງຊຸດຖືກ disjoint

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) ບ່ອນທີ່ "m" ແລະ "n" ແມ່ນ ຈຳ ນວນຂອງສ່ວນປະກອບໃນຊຸດ 1 ແລະ set2 ຕາມ ລຳ ດັບ ຫນ້າທໍາອິດ, ພວກເຮົາເຂົ້າໄປໃນອົງປະກອບທັງຫມົດຂອງຊຸດທໍາອິດເຂົ້າໄປໃນ HashSet ເຊິ່ງປະກອບສ່ວນສໍາລັບເວລາ O (N) ສັບສົນ. ຫຼັງຈາກນັ້ນ, ພວກເຮົາຂ້າມອົງປະກອບຂອງຊຸດທີ່ສອງ.

ຄວາມສັບສົນໃນອະວະກາດ

O (ມ) ບ່ອນທີ່ "m"  ແມ່ນຂະ ໜາດ ຂອງຊຸດ ທຳ ອິດ. ພວກເຮົາຍັງສາມາດເພີ່ມປະສິດທິພາບການແກ້ໄຂບັນຫາເພື່ອເກັບຮັກສາອາເລທີ່ມີ ຈຳ ນວນສ່ວນປະກອບ ໜ້ອຍ ສຸດ.