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


Сложный уровень Легко
Часто спрашивают в Набор фактов Поход Кулиза Нагарро Opera Snapdeal
массив Бинарный поиск Hash Ларсен и Тубро Поиск Сортировка

Задача «Как проверить, не пересекаются ли два заданных множества?» утверждает, что предположим, что вам даны два набора в виде массива, скажем, 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. Объявить HashSet.
  2. Вставьте все элементы set1 в HashSet.
  3. Просмотрите все элементы set2 [] и проверьте, содержит ли HashSet какие-либо элементы set2 [].
    1. Если он содержит, то возвращает false.
  4. Верните истину.

объяснение

Мы дали постановку задачи, в которой предлагается выяснить, являются ли два заданных набора непересекающимися наборами или нет. Оба набора представлены в виде массива. Мы будем использовать HashSet и унаследуем свойства HashSet. HashSet не позволяет хранить повторяющиеся значения.

Объявить  Логический функция, которая просто возвращает либо истину, либо ложь. Мы передадим в эту логическую функцию два массива, и первое, что она сделает, это сохранит значение set1 [] в HashSet, и после сохранения в нем каждого значения set1 [] он проверит, содержит ли HashSet какие-либо элементы set2 [ ]. Он возвращает false, что означает, что set1 [] и set2 [] имеют общий элемент. Таким образом, это не непересекающиеся множества и возвращает false.

Смотрите также
Решение 3Sum Leetcode

Давайте рассмотрим здесь пример, мы возьмем два набора и выполним на них наш алгоритм:

Set1 [] = {2, 1, 6, 9, 7}

Set2 [] = {4, 2, 19, 3}

HashSet myset;

Чтобы сохранить значение set1 в HashSet, мы пройдем по каждому из элементов set1 и вставим все элементы в myset.

Для set1 []

i = 0, myset = {2}

я = 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. Обход set2 [] = {4, 2, 19, 3};

j = 0, set2 [j] = 4

myset не найдет 4 в HashSet

j = 0, set2 [j] = 2

myset найдет 2 в HashSet, поэтому он вернет false, а наш вывод напечатает «Это не непересекающиеся наборы». В случае, если какой-либо из элементов set2 [] не соответствует в myset, он выйдет из цикла и вернет true.

Код 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

Код Java для проверки, не пересекаются ли два набора  

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

Анализ сложности  

Сложность времени

О (т + п) в котором «М» и «Н» - количество элементов в наборах set1 и set2 соответственно. Сначала мы вводим все элементы первого набора в HashSet, что увеличивает временную сложность O (N). Затем обходим элементы второго набора.

Смотрите также
Сортировка целых чисел по количеству 1-битных решений Leetcode

Космическая сложность

О (м) в котором «М»  размер первого набора. Мы также можем оптимизировать решение для хранения массива с минимальным количеством элементов.