如何檢查兩組是否不相交？

目的是檢查兩個集的不相交與否，這裏是到目前爲止的代碼：如何檢查兩組是否不相交？

#include <iostream> 
#include <cstdlib> 
#include <unordered_set> 
using namespace std; 

bool isDisjoint(int set1[], int len1, int set2[], int len2); 
int main() 
{ 
    int set1[] = {10, 5, 3, 4, 6}; 
    int set2[] = {8, 7, 9, 3}; 
    if (isDisjoint(set1,sizeof(set1),set2,sizeof(set2))) 
     cout<<"DISJOINT"; 
    else 
     cout<<"NOT DISJOINT"; 

    return 0; 
} 

bool isDisjoint(int set1[], int len1, int set2[], int len2) 
{ 
    unordered_set<int> set; 


    for(int i=0;i<len1;i++) 
     set.insert(set1[i]); 

    for(int j=0;j<len2;j++) 
    { 
     if(set2[j]==set.find(set2[j])) 
    //-----------^^^^----------------- 
      return false; 

    } 

    return true; 
}

然而，如圖評論，我得到一個問題，當我嘗試檢查元素是否存在無序集合：

無效的操作數的二進制表達式（ 'INT' 和 '遊標'（又名 '__hash_const_iterator *>'））

我試圖指請打開文檔this和this，但它無助於解決問題，但由於我來自Java背景，使我更加困惑。任何幫助解決這個問題將不勝感激！謝謝。

來源

2017-09-16 OBX

查看[std :: set_difference]（http://en.cppreference.com/w/cpp/algorithm/set_difference） –

@JesperJuhl - 「std :: set_difference」需要**排序的**輸入序列;儘管有其名稱，但它不適用於未分類集。 –

如果你想使用O（n^2）算法，你不需要將數據複製到那些中間的'std :: unordered_set';只需在數組上進行搜索和比較。對於更大的數據集，可以對數組進行排序或將數據複製到兩個「std :: set」對象中，然後使用「std :: set_difference」。 –

支票應該是針對set.end()而不是針對set2[j]：

if (set.find(set2[j]) != set.end()) { 
    ... 
}

請注意，您撥打isDisjoint傳遞sizeof(set1)和sizeof(set2)，這是不正確的：你應該通過sizeof(set1)/sizeof(set1[0])或std::size(set1)在C++ 17。

來源

2017-09-16 09:11:15 dasblinkenlight

這很有趣，我運行該程序，併成功運行，爲什麼使用sizeof（set1）不正確？：/ – OBX

@OBX因爲'sizeof'以字節爲單位返回大小。在你的程序中，在32位平臺上'sizeof（set1）'是20.'isDisjoint'將使用數組中的五個項目，之後是15個「垃圾」項目。這種行爲是不確定的：您可能得到錯誤的答案或崩潰。 – dasblinkenlight

find返回iterator，參見this。

只是

if(set.find(set2[j]) != set.end())

此外，sizeof(set1)返回尺寸替代

if(set2[j]==set.find(set2[j]))

在組字節。爲了得到真實的號碼，你擁有的元素個數由sizeof(int)劃分，因此：

sizeof(set1)/sizeof(int)

這將打開這行代碼：

if (isDisjoint(set1,sizeof(set1),set2,sizeof(set2)))

成這樣：

int set1_size = sizeof(set1)/sizeof(int); 
int set2_size = sizeof(set2)/sizeof(int); 

if (isDisjoint(set1,set1_size,set2,set2_size) 
    //blah blah the rest

來源

2017-09-16 09:08:30 magicleon

如何檢查兩組是否不相交？

回答

相關問題