如何檢查兩個給定的集合是否不相交?  


難度級別 容易獎學金
經常問 事實集 遠足 庫利扎 長郎 Opera 瀏灠器 Snapdeal
排列 二元搜尋 哈希 拉森和圖布羅 搜索 排序

問題“如何檢查兩個給定的集合是否不相交?” 假設您得到了兩個數組形式的集合,分別是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. 將set1的所有元素插入HashSet。
  3. 遍歷set2 []的所有元素,並檢查HashSet是否包含set2 []的任何元素。
    1. 如果包含,則返回false。
  4. 返回true。

解釋

我們給出了一個問題陳述,要求找出兩個給定集合是否不相交集合。 這兩個集合都表示為一個數組。 我們將使用HashSet並繼承HashSet的屬性。 HashSet不允許存儲重複值。

聲明一個  布爾 僅返回true或false的函數。 我們將兩個數組傳遞給該布爾函數,它要做的第一件事是將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}

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 []的元素(如果有)。 遍歷set2 [] = {4,2,19,3};

j = 0,set2 [j] = 4

myset在HashSet中找不到4

j = 0,set2 [j] = 2

我的 將在HashSet中找到2,因此它將返回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

複雜度分析  

時間複雜度

O(米+ n) 哪裡 “m”個 “ n” 是set1和set2中元素的數量。 首先,我們將第一個集合的所有元素輸入到HashSet中,這會增加O(N)時間的複雜度。 然後我們遍歷第二組的元素。

也可以看看
按1位Leetcode解決方案的數量對整數進行排序

空間複雜度

O(米) 哪裡 “m”個  是第一組的大小。 我們還可以優化解決方案,以存儲元素數量最少的數組。