តើធ្វើដូចម្តេចដើម្បីពិនិត្យមើលថាតើឈុតពីរដែលបានផ្តល់ឱ្យត្រូវបាន disjoint?


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ រោងចក្រ ការដំឡើង គុលលីហ្សា ណាហ្គារ៉ូ ល្ខោនអូប៉េរ៉ា Snapdeal
អារេ ការស្វែងរកគោលពីរ ហាស់ ឡាសាននិងធូបូ ការស្វែងរក តម្រៀប

បញ្ហា "តើត្រូវពិនិត្យមើលថាតើឈុតពីរដែលបានផ្តល់ឱ្យត្រូវបានគេស្អប់?" ចែងថាឧបមាថាអ្នកត្រូវបានផ្តល់ជាពីរឈុតក្នុងទំរង់នៃអារេនិយាយថា set1 [] និង set2 [] ។ ភារកិច្ចរបស់អ្នកគឺចង់ដឹងថាតើឈុតទាំងពីរគឺ Disjoint Sets រឺអត់។

ឧទាហរណ៍

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

ការពន្យល់

ដោយសារតែមិនមានធាតុធម្មតានៅក្នុងសំណុំទាំងពីរដូច្នេះពួកគេត្រូវបាន disjoint សំណុំ

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

ការពន្យល់

នៅទីនេះ ២ គឺជាធាតុទូទៅមួយនៅក្នុងសំណុំទាំងពីរដូច្នេះពួកគេមិនត្រូវបាន disjoint សំណុំ។

ក្បួនដោះស្រាយ

  1. ប្រកាសក ហាស់សេត.
  2. បញ្ចូលធាតុទាំងអស់នៃឈុត ១ ទៅហាស់សេត។
  3. ឆ្លងកាត់រាល់ធាតុទាំងអស់នៃ set2 [] ហើយពិនិត្យមើលថាតើហាសាសេតមានធាតុណាមួយនៃ set2 [] ដែរឬទេ។
    1. ប្រសិនបើវាមាន, បន្ទាប់មកត្រឡប់មកវិញមិនពិត។
  4. ត្រឡប់ពិត។

ការពន្យល់

យើងបានផ្តល់សេចក្តីថ្លែងការណ៍អំពីបញ្ហាដែលស្នើសុំឱ្យរកមើលថាតើឈុតដែលបានផ្តល់ឱ្យទាំងពីរគឺជាឈុតដែលមិនពេញចិត្តឬអត់។ ឈុតទាំងពីរត្រូវបានតំណាងជាអារេ។ យើងនឹងប្រើហាសសេតហើយទទួលមរតកនូវលក្ខណៈសម្បត្តិរបស់ហាសសេត។ ហាស់សេតមិនអនុញ្ញាតឱ្យរក្សាទុកតម្លៃជាន់គ្នាទេ។

ប្រកាសក  ប៊ូលីន មុខងារដែលគ្រាន់តែត្រឡប់ពិតឬមិនពិត។ យើងនឹងបញ្ជូនអារេពីរទៅកាន់មុខងារប៊ូលីនហើយរឿងដំបូងដែលវាត្រូវធ្វើគឺរក្សាទុកតម្លៃនៃសំណុំ ១ [] ទៅហាស់សិនហើយបន្ទាប់ពីរក្សាទុកតម្លៃនីមួយៗនៅក្នុងសំណុំនៃសំណុំ ១ [] វានឹងពិនិត្យមើលថាតើហាសាតមានធាតុណាមួយនៃឈុត ២ ដែរឬទេ [ ] ។ វាត្រឡប់មិនពិតមានន័យថាសំណុំ ១ [] និងសំណុំ ២ [] មានធាតុរួម។ ដូច្នេះទាំងនេះមិនមែនជាសំណុំ disjoint និងត្រឡប់មិនពិត។

សូមឱ្យយើងពិចារណាឧទាហរណ៍នៅទីនេះយើងនឹងយកសំណុំពីរហើយអនុវត្តក្បួនដោះស្រាយរបស់យើងនៅលើវា:

ឈុត ១ [] = {២, ១, ៦, ៩, ៧}

សំណុំ ២ [] = {៤, ២, ១៩, ៣}

ហាប់សាត។

ចំពោះការរក្សាទុកតម្លៃនៃសំណុំ ១ ទៅហាដសេតយើងនឹងឆ្លងធាតុនីមួយៗនៃសិត ១ ហើយបញ្ចូលធាតុទាំងអស់ទៅក្នុង“ អុហ្វសិត” ។

សម្រាប់សំណុំ ១ []

i = 0, myset = {2}

i = 1, myset = {2, 1}

i = 2, myset = {2, 1, 6}

i = 3, myset = {២, ១, ៦, ៩}

i = 4, myset = {២, ១, ៦, ៩, ៧}

យើងមានហាសតារបស់យើង។ យើងទន្ទឹងរងចាំរកធាតុនៃសំណុំ ២ [] (បើមាន) ក្នុងហាសសេត។ ដំណើរឆ្លងកាត់សំណុំទី ២ [] = {៤, ២, ១៩, ៣};

j = 0, សំណុំ ២ [ចា] = ៤

myset នឹងមិនរកឃើញ 4 នៅក្នុងហាស់សេតទេ

j = 0, សំណុំ ២ [ចា] = ៤

myset នឹងរកឃើញ ២ នៅក្នុងហាស់សេតដូច្នេះវានឹងមិនពិតហើយការបោះពុម្ពលទ្ធផលរបស់យើង“ ទាំងនេះមិនត្រូវបានកំណត់ទេ” ។ ក្នុងករណីប្រសិនបើមានធាតុណាមួយនៃ set2 [] មិនត្រូវគ្នានឹងចំនុចចាប់ផ្តើមនោះវានឹងចេញពីរង្វិលជុំហើយត្រលប់មកវិញជាការពិត។

លេខកូដ 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

កូដចាវ៉ាដើម្បីពិនិត្យមើលថាតើឈុតពីរត្រូវបាន 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” គឺជាចំនួនធាតុក្នុងសំណុំ ១ និងសំណុំ ២ រៀង ៗ ខ្លួន។ ដំបូងយើងបញ្ចូលធាតុទាំងអស់នៃសំណុំដំបូងទៅហាដសេតដែលរួមចំណែកដល់ភាពស្មុគស្មាញពេលវេលាអូ។ បន្ទាប់មកយើងឆ្លងកាត់ធាតុនៃឈុតទីពីរ។

ភាពស្មុគស្មាញនៃលំហ

O (ម) ដែលជាកន្លែងដែល "m"  គឺជាទំហំនៃឈុតដំបូង។ យើងក៏អាចបង្កើនប្រសិទ្ធភាពដំណោះស្រាយដើម្បីរក្សាទុកអារេដែលមានចំនួនអប្បបរមានៃធាតុ។