我在算法课上遇到了一个问题,但是我无法解决它。这个问题要求我们设计一种排序算法,其时间复杂度为 O(nlogn)
,并且使用二分查找进行搜索,时间复杂度为 O(log n)
。给定两个集合 P
和 Q
,我需要设计一个算法来确定这两个集合是否不相交。
我在算法课上遇到了一个问题,但是我无法解决它。这个问题要求我们设计一种排序算法,其时间复杂度为 O(nlogn)
,并且使用二分查找进行搜索,时间复杂度为 O(log n)
。给定两个集合 P
和 Q
,我需要设计一个算法来确定这两个集合是否不相交。
O(N)
解决方案(假设两个集合已排序):
- 合并带有元素属于哪个集合信息的两个已排序集合
- 遍历合并列表,如果您发现来自两个集合的两个相等元素,则不是不交集,否则,如果能够到达末尾,则是不交集
例如:
a= 1, 4, 6
b= 2, 4, 7
现在合并集合为:
元素: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];
希望我表述清楚了。只有当两个集合之间没有共同元素时,它们才是不相交的。我假设这两个集合都有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.