使用查找和排序的不相交集合

Question

我在算法课上遇到了一个问题，但是我无法解决它。这个问题要求我们设计一种排序算法，其时间复杂度为 O(nlogn)，并且使用二分查找进行搜索，时间复杂度为 O(log n)。给定两个集合 P 和 Q，我需要设计一个算法来确定这两个集合是否不相交。

- Shaurya Chaudhuri

Answer 1

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

1. 合并带有元素属于哪个集合信息的两个已排序集合
2. 遍历合并列表，如果您发现来自两个集合的两个相等元素，则不是不交集，否则，如果能够到达末尾，则是不交集

例如：

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]; 希望我表述清楚了。

- Trying

---

假设两个集合已经排序好了，你是对的。为了得到你的解决方案，可以修改合并算法，在合并时只检查两个元素是否相等或不相等。 - iampat

@Trying，你能给出一个实际的方法来存储一组数字的信息吗？我的意思是，如果它是一个int数组，你会使用哪种容器？ - java_doctor_101

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.

- java_doctor_101

---

只需确保首先对集合进行排序（另一个O(n log n)操作），以便每个搜索都可以在O(n)时间内完成。 - Ted Hopp

如果在搜索之前两个列表都被排序，时间复杂度将是O（nlogn）+ O（nlogn）+ O（nlogn）= O（nlogn）[2次排序和一次搜索]。对吗？ @TedHopp - 如果使用二分搜索将需要O（logn），如果使用线性搜索，则为O（n），但由于它在另一个循环内，因此它将是O（n ^ 2）。 - Shaurya Chaudhuri

@Ted，请问你能解释一下如何在两个已排序数组中搜索共同元素只需要n的时间吗？ - java_doctor_101

嗯，那应该是O(log n)。抱歉，打字太快了。 - Ted Hopp