高效数据结构用于查找两个列表的交集

Question

我有两个非常大的List<List<int>> A和B。我需要找到这些列表中每个元素之间的交集。

A[0] = { 1, 2, 3};
B[0] = {2, 3, 4};

Intersection = { 2, 3 };

我的实现：

List<int> intersection = A[0].Intersection(B[0]).ToList();

这个解决方案时间非常长。我想知道是否有更好的方法来做这件事以及是否有更有效的数据结构可以在更短的时间内执行。

谢谢！

- John Latham

---

好问题 - 这会让事情变得更容易。 - BrokenGlass

只需要对一个集合进行排序，就可以使用二分查找。选择一个。OP的问题与关系数据库中的外键查找完全类似。未指定A或B是否允许具有重复值，以及如果存在重复值应该发生什么。 - user1899861

Answer 1

在C#中，你应该使用一个Hashset，例如HashSet<T>，在哈希集合中进行查找的时间复杂度为O(1)（如果使用了合适的哈希函数和数组作为底层数据结构），而列表的时间复杂度则为O(n)。

在C#中使用Linq，你基本上可以“内置”这个功能：Intersect()会在内部使用哈希集合来计算交集，时间复杂度为O(n)，而不是使用两个列表时的O(n^2)。

var intersection = a.Intersect(b).ToList();

- BrokenGlass

---

太好了！谢谢。那么.ToList()会产生额外的O(N)复杂度，我该如何避免它呢？ - John Latham

这可能是最好的解决方案，但值得记住的是，O(1)的算法仍然可能比O(n)的算法慢。这些特征并不指定完成搜索所需的时间，而是指定随着集合大小增加，时间如何变化。一个昂贵的哈希计算可能表现不如O(n)的简单比较。这是哈希表几乎从未达到人们对二分查找期望的普遍忽视的原因之一。 - user1899861

Answer 2

使用HashSet(T).IntersectWith的代码示例：

HashSet<string> lst1 = new HashSet<string> 

     { "id1", "id2", "id3" };

HashSet<string> lst2 = new HashSet<string> 

     { "id2", "id3", "id4" };

// what happens is that, lst1 will be modified by only leaving the intersect items
lst1.IntersectWith(lst2);

PS：我使用了字符串的示例，但您可以使用自己的整数值。

- aspiring