检查两个给定的集合是否不相交?
当两个集合没有公共元素时,它们是不相交的集合。换句话说,如果我们得到两个集合的交集,那么我们将得到空集合。
该方法很简单,该算法给出了两组。我们假设两个集合都已排序,并且在两个集合之间比较了项目。当存在匹配项时,它不是不相交集,当没有项目匹配时,它们就是不相交集。
输入输出
Input:Two sets:
set1: {15, 12, 36, 21, 14}
set2: {7, 89, 56, 32}
Output:
Both sets are disjoint
算法
isDisjoint(set1, set2)
输入:两套。
输出:当两个集合不相交时为真。
Begini1 := start of first set
i2 := start of second set
while i1 in set1 and i2 in set 2, do
if set1[i1] < set2[i2], then
i1 := i1 + 1
else if set2[i2] < set1[i1], then
i2 := i2 + 1
else
return false
done
return true
End
示例
#include<iostream>#include<set>
using namespace std;
bool isDisjoint(set<int> set1, set<int> set2) {
set<int>::iterator i1, i2;
i1 = set1.begin(); i2 = set2.begin(); //initialize iterators with first element
while(i1 != set1.end() && i2 != set2.end()) { //when both set have some elements to check
if(*i1 < *i2)
i1++; //when item of first set is less than second set
else if(*i2 < *i1)
i2++; //when item of second set is less than first set
else
return false; //if items are matched, sets are not disjoint
}
return true;
}
int main() {
set<int> set1, set2;
int n1, n2;
cout << "Enter number of elements in set 1: "; cin >>n1;
while(n1 != set1.size()) { //duplicate items will be discarded
int item;
cout << "Enter element: "; cin >> item;
set1.insert(item);
}
cout << "Enter number of elements in set 2: "; cin >>n2;
while(n2 != set2.size()) {
int item;
cout << "Enter element: "; cin >> item;
set2.insert(item);
}
if(isDisjoint(set1, set2))
cout << "Both sets are disjoint";
else
cout << "Sets are not disjoint";
}
输出结果
Enter number of elements in set 1: 5Enter element: 15
Enter element: 12
Enter element: 36
Enter element: 21
Enter element: 14
Enter number of elements in set 2: 4
Enter element: 7
Enter element: 89
Enter element: 56
Enter element: 32
Both sets are disjoint
以上是 检查两个给定的集合是否不相交? 的全部内容, 来源链接: utcz.com/z/322422.html