使用搜索和排序进行脱节设置

Question

我的算法类中有一个问题,我无法解决它.问题表明Theres是一种排序算法,O(nlogn)搜索是通过二进制搜索完成的O(log n).给出两个集合P&Q我必须设计一个算法来确定这两个集合是否是不相交的.

Answer 1

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

1. 合并两个有序集合,其中包含元素属于哪个集合的信息
2. 遍历合并列表,如果你发现两个相同的元素来自两个集合,而不是不相交,如果能够达到最终而不是不相交

例如

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

现在合并set =

内容: 1 2 4 4 6 7

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

现在我们可以清楚地看到两个四肢是连续的,两个都来自两个不同的集合,因此不是不相交的.

编辑:

如果你需要找到的是不相交的或不是简单的合并会给你那些.一旦你发现集合中的两个元素都是相等的,只要返回说不是不相交,如果能够到达两者的结尾而不是不相交.

与容器有关的问题.以下是:

class Element{
int i;
int setInfo
}

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

希望我很清楚.