Рубрики

Как проверить, не пересекаются ли два заданных множества?

Учитывая два набора, представленные двумя массивами, как проверить, являются ли эти два набора непересекающимися или нет? Можно предположить, что данные массивы не имеют дубликатов.

Input: set1[] = {12, 34, 11, 9, 3}
       set2[] = {2, 1, 3, 5}
Output: Not Disjoint
3 is common in two sets.

Input: set1[] = {12, 34, 11, 9, 3}
       set2[] = {7, 2, 1, 5}
Output: Yes, Disjoint
There is no common element in two sets.

Существует множество способов решения этой проблемы, это хороший тест, чтобы проверить, сколько решений вы можете угадать.

Способ 1 (простой)
Итерируйте по каждому элементу первого набора и ищите его в другом наборе, если какой-либо элемент найден, верните false. Если элемент не найден, вернуть дерево. Временная сложность этого метода составляет O (mn).

Ниже приведена реализация вышеуказанной идеи.

C ++

// Простая программа на C ++, чтобы проверить, не пересекаются ли два набора
#include<iostream>

using namespace std;

  
// Возвращает true, если set1 [] и set2 [] не пересекаются, иначе false

bool areDisjoint(int set1[], int set2[], int m, int n)

{

    // Взять каждый элемент set1 [] и найти его в set2

    for (int i=0; i<m; i++)

      for (int j=0; j<n; j++)

         if (set1[i] == set2[j])

            return false;

  

    // Если в set2 нет элемента set1

    return true;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int set1[] = {12, 34, 11, 9, 3};

    int set2[] = {7, 2, 1, 5};

    int m = sizeof(set1)/sizeof(set1[0]);

    int n = sizeof(set2)/sizeof(set2[0]);

    areDisjoint(set1, set2, m, n)? cout << "Yes" : cout << " No";

    return 0;

}

Джава

// Java-программа для проверки, если два набора не пересекаются

  

public class disjoint1 

{

    // Возвращает true, если set1 [] и set2 []

    // дизъюнкт, иначе ложь

    boolean aredisjoint(int set1[], int set2[]) 

    {

         // Взять каждый элемент set1 [] и

         // ищем его в set2

        for (int i = 0; i < set1.length; i++) 

        {

            for (int j = 0; j < set2.length; j++) 

            {

                if (set1[i] == set2[j])

                    return false;

            }

        }

        // Если в set2 нет элемента set1

        return true;

    }

      

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args) 

    {

        disjoint1 dis = new disjoint1();

        int set1[] = { 12, 34, 11, 9, 3 };

        int set2[] = { 7, 2, 1, 5 };

  

        boolean result = dis.aredisjoint(set1, set2);

        if (result)

            System.out.println("Yes");

        else

            System.out.println("No");

    }

}

  
// Этот код предоставлен Rishabh Mahrsee

питон

# Простая программа на Python 3 для проверки
# если два набора не пересекаются

  
# Возвращает true, если set1 [] и set2 [] не пересекаются, иначе false

def areDisjoint(set1, set2, m, n):

    # Взять каждый элемент set1 [] и найти его в set2

    for i in range(0, m):

        for j in range(0, n):

            if (set1[i] == set2[j]):

                return False

  

    # Если в set2 нет элемента set1

    return True

  

  
# Драйверная программа

set1 = [12, 34, 11, 9, 3]

set2 = [7, 2, 1, 5]

m = len(set1)

n = len(set2)

print("yes") if areDisjoint(set1, set2, m, n) else(" No")

  
# Этот код предоставлен Смитой Динеш Семвал

C #

// C # программа для проверки, если два
// множества не пересекаются

using System;

  

class GFG

{
// Возвращает true, если set1 [] и set2 []
// не пересекаются, иначе ложь

public virtual bool aredisjoint(int[] set1, 

                                int[] set2)

{

    // Взять каждый элемент set1 []

    // и ищем его в set2

    for (int i = 0; i < set1.Length; i++)

    {

        for (int j = 0; 

                 j < set2.Length; j++)

        {

            if (set1[i] == set2[j])

            {

                return false;

            }

        }

    }

      

    // Если нет элемента set1

    // присутствует в set2

    return true;

}

  
// Код драйвера

public static void Main(string[] args)

{

    GFG dis = new GFG();

    int[] set1 = new int[] {12, 34, 11, 9, 3};

    int[] set2 = new int[] {7, 2, 1, 5};

  

    bool result = dis.aredisjoint(set1, set2);

    if (result)

    {

        Console.WriteLine("Yes");

    }

    else

    {

        Console.WriteLine("No");

    }

}
}

  
// Этот код предоставлен Shrikant13

PHP

<?php
// Простая PHP-программа для проверки
// если два множества не пересекаются

  
// Возвращает true, если set1 [] и set2 []
// не пересекаются, иначе ложь

function areDisjoint($set1, $set2, $m, $n)

{

    // Взять каждый элемент set1 []

    // и ищем его в set2

    for ($i = 0; $i < $m; $i++)

    for ($j = 0; $j < $n; $j++)

        if ($set1[$i] == $set2[$j])

            return false;

  

    // Если нет элемента set1

    // присутствует в set2

    return true;

}

  
// Код драйвера

$set1 = array(12, 34, 11, 9, 3);

$set2 = array(7, 2, 1, 5);

$m = sizeof($set1);

$n = sizeof($set2);

if(areDisjoint($set1, $set2,

               $m, $n) == true)

    echo "Yes";

else

    echo " No";

  
// Этот код добавлен
// Аканкша Рай
?>


Выход :

Yes

Способ 2 (использовать сортировку и объединение)
1) Сортировать первый и второй наборы.
2) Используйте процесс слияния как для сравнения элементов.

Ниже приведена реализация вышеуказанной идеи.

C ++

// Простая программа на C ++, чтобы проверить, не пересекаются ли два набора
#include<iostream>
#include<algorithm>

using namespace std;

  
// Возвращает true, если set1 [] и set2 [] не пересекаются, иначе false

bool areDisjoint(int set1[], int set2[], int m, int n)

{

    // Сортировка заданных двух наборов

    sort(set1, set1+m);

    sort(set2, set2+n);

  

    // Проверяем одинаковые элементы, используя процесс слияния

    int i = 0, j = 0;

    while (i < m && j < n)

    {

        if (set1[i] < set2[j])

            i++;

        else if (set2[j] < set1[i])

            j++;

        else / * если set1 [i] == set2 [j] * /

            return false;

    }

  

    return true;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int set1[] = {12, 34, 11, 9, 3};

    int set2[] = {7, 2, 1, 5};

    int m = sizeof(set1)/sizeof(set1[0]);

    int n = sizeof(set2)/sizeof(set2[0]);

    areDisjoint(set1, set2, m, n)? cout << "Yes" : cout << " No";

    return 0;

}

Джава

// Java-программа для проверки, если два набора не пересекаются

  

import java.util.Arrays;

  

public class disjoint1 

{

    // Возвращает true, если set1 [] и set2 []

    // дизъюнкт, иначе ложь

    boolean aredisjoint(int set1[], int set2[]) 

    {

        int i=0,j=0;

          

        // Сортировка заданных двух наборов

        Arrays.sort(set1);

        Arrays.sort(set2);

          

        // Проверяем одинаковые элементы используя

        // объединить как процесс

        while(i<set1.length && j<set2.length)

        {

            if(set1[i]<set2[j])

                i++;

            else if(set1[i]>set2[j])

                j++;

            else 

                return false;

              

        }

        return true;

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args) 

    {

        disjoint1 dis = new disjoint1();

        int set1[] = { 12, 34, 11, 9, 3 };

        int set2[] = { 7, 2, 1, 5 };

  

        boolean result = dis.aredisjoint(set1, set2);

        if (result)

            System.out.println("YES");

        else

            System.out.println("NO");

    }

}

  
// Этот код предоставлен Rishabh Mahrsee

питон

# Простая программа на Python 3 для проверки
# если два набора не пересекаются

  
# Возвращает true, если set1 [] и set2 []
# не пересекаются, иначе ложь

def areDisjoint(set1, set2, m, n):

    # Сортировать данные два набора

    set1.sort()

    set2.sort()

  

    # Проверка на те же элементы

    # используя процесс слияния

    i = 0; j = 0

    while (i < m and j < n):

          

        if (set1[i] < set2[j]):

            i += 1

        elif (set2[j] < set1[i]):

            j += 1

        else: # если set1 [i] == set2 [j]

            return False

    return True

  

  
Код водителя

set1 = [12, 34, 11, 9, 3]

set2 = [7, 2, 1, 5]

m = len(set1)

n = len(set2)

  

print("Yes") if areDisjoint(set1, set2, m, n) else print("No")

  
# Этот код предоставлен Смитой Динеш Семвал

C #

// C # программа для проверки, если два набора не пересекаются

using System;

  

public class disjoint1 

{

    // Возвращает true, если set1 [] и set2 []

    // дизъюнкт, иначе ложь

    Boolean aredisjoint(int []set1, int []set2) 

    {

        int i = 0, j = 0;

          

        // Сортировка заданных двух наборов

        Array.Sort(set1);

        Array.Sort(set2);

          

        // Проверяем одинаковые элементы используя

        // объединить как процесс

        while(i < set1.Length && j < set2.Length)

        {

            if(set1[i] < set2[j])

                i++;

            else if(set1[i] > set2[j])

                j++;

            else

                return false;

              

        }

        return true;

    }

  

    // Код драйвера

    public static void Main(String[] args) 

    {

        disjoint1 dis = new disjoint1();

        int []set1 = { 12, 34, 11, 9, 3 };

        int []set2 = { 7, 2, 1, 5 };

  

        Boolean result = dis.aredisjoint(set1, set2);

        if (result)

            Console.WriteLine("YES");

        else

            Console.WriteLine("NO");

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход :

Yes

Временная сложность вышеуказанного решения составляет O (mLogm + nLogn).

Вышеупомянутое решение сначала сортирует оба множества, затем занимает O (m + n) время, чтобы найти пересечение. Если нам дают, что входные наборы отсортированы, то этот метод является лучшим среди всех.

Метод 3 (использовать сортировку и бинарный поиск)
Это похоже на метод 1. Вместо линейного поиска мы используем бинарный поиск .
1) Сортировка первого набора.
2) Итерируйте по каждому элементу второго набора и используйте бинарный поиск для поиска каждого элемента в первом наборе. Если элемент найден, верните его.

Временная сложность этого метода составляет O (mLogm + nLogm)

Метод 4 (Использование бинарного дерева поиска)
1) Создайте самобалансирующееся двоичное дерево поиска ( Red Black , AVL , Splay и т. Д.) Для всех элементов в первом наборе.
2) Перебирайте все элементы второго набора и ищите каждый элемент в построенном выше бинарном дереве поиска. Если элемент найден, вернуть false.
3) Если все элементы отсутствуют, вернуть true.

Временная сложность этого метода составляет O (mLogm + nLogm).

Метод 5 (использовать хеширование)
1) Создать пустую хеш-таблицу.
2) Переберите первый набор и сохраните каждый элемент в хэш-таблице.
3) Переберите второй набор и проверьте, присутствует ли какой-либо элемент в хеш-таблице. Если присутствует, вернуть false, иначе игнорировать элемент.
4) Если все элементы второго набора отсутствуют в хеш-таблице, вернуть true.

Ниже приводится реализация этого метода.

C / C ++

#include<bits/stdc++.h>

using namespace std;

  
/ * C ++ программа для проверки, различны ли два набора * /
// Эта функция печатает все отдельные элементы

bool areDisjoint(int set1[], int set2[], int n1, int n2)

{

    // Создает пустой хэшсет

    set<int> myset;

  

    // Обходим первый набор и сохраняем его элементы в хэше

    for (int i = 0; i < n1; i++)

        myset.insert(set1[i]);

  

    // Обходим второй набор и проверяем, есть ли в нем какой-либо элемент

    // уже в хеше или нет.

    for (int i = 0; i < n2; i++)

        if (myset.find(set2[i]) != myset.end())

            return false;

  

    return true;

}

  
// Метод драйвера для проверки вышеуказанного метода

int main()

{

    int set1[] = {10, 5, 3, 4, 6};

    int set2[] = {8, 7, 9, 3};

  

    int n1 = sizeof(set1) / sizeof(set1[0]);

    int n2 = sizeof(set2) / sizeof(set2[0]);

    if (areDisjoint(set1, set2, n1, n2))

        cout << "Yes";

    else

        cout << "No";

}
// Эта статья предоставлена Чхави

Джава

/ * Java-программа для проверки, различны ли два набора * /

import java.util.*;

  

class Main

{

    // Эта функция печатает все отдельные элементы

    static boolean areDisjoint(int set1[], int set2[])

    {

        // Создает пустой хэшсет

        HashSet<Integer> set = new HashSet<>();

  

        // Обходим первый набор и сохраняем его элементы в хэше

        for (int i=0; i<set1.length; i++)

            set.add(set1[i]);

  

        // Обходим второй набор и проверяем, есть ли в нем какой-либо элемент

        // уже в хеше или нет.

        for (int i=0; i<set2.length; i++)

            if (set.contains(set2[i]))

                return false;

  

        return true;

    }

  

    // Метод драйвера для проверки вышеуказанного метода

    public static void main (String[] args)

    {

        int set1[] = {10, 5, 3, 4, 6};

        int set2[] = {8, 7, 9, 3};

        if (areDisjoint(set1, set2))

            System.out.println("Yes");

        else

            System.out.println("No");

    }

}

C #

using System;

using System.Collections.Generic;

  
/ * C # программа для проверки, различны ли два набора * /

  

public class GFG

{

    // Эта функция печатает все отдельные элементы

    public static bool areDisjoint(int[] set1, int[] set2)

    {

        // Создает пустой хэшсет

        HashSet<int> set = new HashSet<int>();

  

        // Обходим первый набор и сохраняем его элементы в хэше

        for (int i = 0; i < set1.Length; i++)

        {

            set.Add(set1[i]);

        }

  

        // Обходим второй набор и проверяем, есть ли в нем какой-либо элемент

        // уже в хеше или нет.

        for (int i = 0; i < set2.Length; i++)

        {

            if (set.Contains(set2[i]))

            {

                return false;

            }

        }

  

        return true;

    }

  

    // Метод драйвера для проверки вышеуказанного метода

    public static void Main(string[] args)

    {

        int[] set1 = new int[] {10, 5, 3, 4, 6};

        int[] set2 = new int[] {8, 7, 9, 3};

        if (areDisjoint(set1, set2))

        {

            Console.WriteLine("Yes");

        }

        else

        {

            Console.WriteLine("No");

        }

    }

}
// Этот код предоставлен Shrikant13


Выход:

No

Временная сложность описанной выше реализации составляет O (m + n) в предположении, что операции хэширования, такие как add () и contains (), работают за O (1) времени.

Эта статья предоставлена Радживом . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Как проверить, не пересекаются ли два заданных множества?

0.00 (0%) 0 votes