algorithm - 使用搜索和排序的不相交集

Question

我在算法课上遇到一道题，但我无法解决。问题指出 Theres 是一个具有 O(nlogn) 的排序算法，搜索是通过采用 O(log n) 的二进制搜索完成的。 给定两个集合 P &Q 我必须设计一个算法来确定这两个集合是否不相交。

Answer 1

O(N) 解决方案(假设这两个集合已排序):

1. merge two sorted sets with information like the element belongs to which set
2. traverse through the merge list , if you find two equal elements from two sets than not disjoint else if are able to reach till end than disjoint

例如

a= 1, 4, 6
b= 2, 4, 7

现在合并set=

元素: 1 2 4 4 6 7

设置否(a/b): 1 2 1 2 1 2

现在我们可以清楚地看到两个 fours 是连续的，并且都来自两个不同的集合，因此不相交。

编辑:

如果您需要查找集合是否不相交，那么简单的合并就能满足您的需求。一旦您发现集合中的两个元素都相等，就返回说 not disjoint else if are able to reach till the end of both than disjoint。

与容器相关的问题。下面是:

class Element{
int i;
int setInfo
}

现在将数组声明为:Element[] e=new Element[X];

希望我说清楚了。