c# - 查找两个列表交集的高效数据结构

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();

该解决方案需要很长时间才能执行。我想知道是否有更好的方法来做到这一点，以及我可以用来在更好的时间执行它的更有效的数据结构。

谢谢！

Answer 1

您应该在 C# 中为此使用 Hashset HashSet<T>。哈希集中的查找是 O(1)（如果像样的哈希函数并在下面使用数组），而不是列表的 O(n)。

在 C# 中使用 Linq，您基本上得到了这个“内置”：Intersect()如果使用两个列表，将在内部使用哈希集来计算 O(n) 而不是 O(n^2) 中的交集。

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

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：我将示例用于字符串，但您可以使用自己的整数值。