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

Question

我的算法课上有一个问题，我无法解决。问题指出 Theres 是一种排序算法，O(nlogn)搜索是通过 Binary searchtaking 完成的O(log n)。两组是给定的P，Q我必须设计一个算法来确定这两组是否不相交。

Answer 1

O(N) solution (assuming the two sets are sorted):

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

e.g.

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

Now merged set=

elements: 1 2 4 4 6 7

set no(a/b): 1 2 1 2 1 2

Now we can clearly see that two fours are consecutive and both are from two different set, hence not disjoint.

EDIT:

If your need is to find the sets are disjoint or not than simple merge will give you that. As soon as you find both elements in the sets are equal than just return saying not disjoint else if are able to reach till end of both than disjoint.

Question related to container. Below is that:

class Element{
int i;
int setInfo
}

Now declare array as: Element[] e=new Element[X];

Hope i am clear.

Answer 2

只有当这两个集合之间没有共同元素时，这两个集合才会不相交。我假设这两个集合每个都有 n 个元素。该算法在 nlog(n) 时间内检查公共元素。如果没有找到共同的元素，则意味着这两个集合是不相交的。

For each element in set "P" search whether that number exist in set "Q".
Time complexity - n*log(n) 
Log(n) to search in set Q and this search will be done "n" times.