高效的数据结构,找到两个列表的交集

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