41

有没有一种算法，给定两个集合，在线性时间内计算它们的交集？

我可以运行两个for循环来检查所有元素对，记录我在两个集合中找到的元素。但是，运行时间将为 O(n 2 )。我如何在 O(n) 时间内做到这一点？

4

6 回答 6

48

这取决于您的设置实现。

如果您有一个散列集（O(1) 查找），那么所有其他海报所指示的方法都是正确的。遍历第一组中的所有元素。如果它在第二组中，则将其添加到结果中。这在 O(n) 时间内运行。

如果您有一个树集（O(lg n) 查找），那么这种方法将起作用，但它在 O(n lg n) 时间内运行。你可以做得更好; 有一个 O(n) 解决方案。我假设您有某种迭代器可以按升序遍历这两个集合的元素。如果你这样做了，那么问题是“给定两个排序顺序的列表，找到它们的交集”。这可以使用用于合并两个范围的算法的修改版本来完成。这个想法是跟踪两个迭代器。在每一步，比较范围的第一个元素。如果它们相等，则将元素添加到交集并向前推进两个迭代器。如果第一个小于第二个，则推进第一个迭代器。如果第一个元素更大，则推进第二个迭代器。

于 2011-01-09T22:18:41.683 回答
12

我想知道没有人提到哈希表。
无论您的 set 实现如何（即使这里的 'set' 表示一个简单的数组），您都可以

  1. 将第一组的内容放入哈希表中，然后
  2. 遍历第二组，检查哈希表是否包含当前元素。

O(n)

于 2011-01-09T22:55:47.067 回答
4 
intersection(a, b):
  result = new empty set
  for x in b:
    if a contains x:
      add x to result

  return result

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

于 2011-01-09T22:14:38.173 回答
2

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

于 2014-02-25T17:58:38.030 回答
0

如果两个列表之一是有序的，那么我们可以从无序列表开始

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
}

Time Complexity = O(n O(BINARY-SEARCH)) = O(n log n)

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

其中 BIG-THETA 是渐近平均值，C是 aconstant 和T(hash)是散列函数所需的时间

于 2012-06-15T13:13:29.993 回答
0

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

于 2011-01-09T22:13:47.037 回答