在线性时间内计算集合交集？

Question

有没有一种算法，可以在线性时间内计算两个集合的交集？

我可以运行两个for循环来检查所有元素对，并记录我在两个集合中发现的元素。然而，运行时间将是O(n²)。如何在O(n)时间内完成此操作？

- NEO

---

为什么会是n^2呢？难道不是“显而易见”的O(n)解决方案吗？我们应该尝试找到更好的解决方案吧？ - pete

@pete 如果要比 O(n) 更好，那么你不能访问集合中的每个元素。如果没有查看该元素，你怎么可能确定关于一个集合元素的任何信息呢？ - michael_teter

@pete，正如问题中明确指出的那样，迭代每对元素作为一种天真的解决方案是O(n^2)。 - Kröw

@Kröw的朴素解决方案是使用HashSet查找，其时间复杂度为O(1)，因此总时间复杂度为O(n)。 - pete

@pete 这一点都不幼稚，请完整阅读问题。 - Kröw

Answer 1

这取决于你的集合实现方式。

如果你使用哈希集合（O(1) 查找），那么其他海报所指出的方法是正确的。遍历第一个集合中的所有元素，如果它也在第二个集合中，就把它加入到结果中。这样做的时间复杂度是 O(n)。

如果你使用树集合（O(lg n) 查找），那么这个方法也可以工作，但它的时间复杂度是 O(n lg n)。你可以通过使用一种 O(n) 的算法来提高效率。我假设你有一种迭代器，能够按照升序遍历两个集合中的元素。如果有这样的迭代器，问题就变成了“给定两个已排序列表，找到它们的交集”。可以使用修改过的合并两个范围的算法来解决。方法是跟踪两个迭代器，在每一步中比较范围的前两个元素。如果它们相等，则将该元素添加到交集中，并将两个迭代器都向前移动。如果第一个元素小于第二个元素，则将第一个迭代器向前移动。如果第一个元素大于第二个元素，则将第二个迭代器向前移动。由于每次迭代至少消耗一个元素，而总共只有 O(n) 个元素，所以该算法的时间复杂度是 O(n)。

- templatetypedef

---

这两个集合没有排序。如果我使用归并排序技术，然后按照您的方法比较范围的第一个元素，但我不确定它是否能在O(n)时间内工作，因为归并排序需要O(nlogn)时间。 - NEO

如果您在O(n lg n)时间内将集合排序，那么这种技术应该可以解决问题，但由于排序开销的原因，它不会以线性时间运行。 您的集合是如何表示的？ - templatetypedef

只需迭代两个列表，将它们添加到哈希表中，然后应用“交集两个哈希表”算法。 - templatetypedef

我想我现在明白了。谢谢。 - NEO

Answer 2

我想知道为什么没有人提到哈希表。

1. 无论你的集合实现方式如何（即使“set”在这里表示简单数组），你都可以将第一个集合的内容放入哈希表中
2. 迭代第二个集合，检查哈希表是否包含当前元素。

O(n)

- Nikita Rybak

---

我不喜欢这个解决方案的唯一问题是它不能扩展到超过两个集合。 - David Bandel

Answer 3

intersection(a, b):
  result = new empty set
  for x in b:
    if a contains x:
      add x to result

  return result

如果contains测试是固定时间（例如在使用哈希表作为实现的集合中），那么这个算法的时间复杂度为O(n)。

- sjr

---

如果a和b是相同的集合，则算法需要O(n^3)的时间，因为在“b”中搜索并将元素添加到“result”需要O(n)的时间。基于数组的集合添加元素需要O(n)的时间，因为集合不能有重复的元素。每次添加都会进行重复检查。如果结果和b基于哈希表，则即使您不能确定搜索和添加需要O(1)的时间，它也可能需要O(n)的时间。 - Viplime

即使集合相等，它也不会花费O(n^3)的时间，而是需要O(3n) = O(n)步骤，假设contains和insert是常数（=O(1)）。 - fkarg

Answer 4

合并这两个数组，并计算每个元素在这个组合数组中的出现次数，并将它们放入一个新的数组中。然后检查这个计数数组是否包含2的条目，这些元素是两个集合的交集。

- user2603796

Answer 5

对于集合1中的所有元素：检查该元素是否在集合2中。您可以实现具有平摊O(1)查找时间的集合。

- Anon.

---

如果您使用基于排序树的集合而不是基于哈希的集合，则可以选择另一种选项：按排序顺序迭代两个集合，推进到当前“最低”集合的下一个元素。总元素数量为O(n)。 - Anon.

Answer 6

如果两个列表中有一个是已排序的，那么我们可以从未排序的列表开始。

FUNCTION: INTERSECTION ( LIST A, LIST B )
{
   CREATE C AS EMPTY LIST

   FOR EVERY: NUMBER n IN A
   {
        IF BINARY-SEARCH(n) IN B
        {
            ADD n TO C
        }
   }

   RETURN C
}

时间复杂度 = O(n O(二分查找)) = O(n log n)

如果列表B被哈希，那么我们有BIG-THETA(C n + T(hash))

其中BIG-THETA是渐近平均值，C是一个常数，T(hash)是哈希函数所需的时间。

- Khaled Khunaifer