我有两个非常大的 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();
此解决方案需要很长时间才能执行。我想知道是否有更好的方法来执行此操作以及我可以使用更有效的数据结构来在更短的时间内执行此操作。
谢谢!
最佳答案
为此，您应该在 C# 中使用哈希集 HashSet<T> .哈希集中的查找是 O(1)(如果使用合适的哈希函数并在下面使用数组)，而不是列表的 O(n)。
在 C# 中使用 Linq 你基本上得到这个“内置”: Intersect() 如果使用两个列表，将在内部使用哈希集来计算 O(n) 而不是 O(n^2) 的交集。
var intersection = a.Intersect(b).ToList();
关于c# - 查找两个列表交集的高效数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14825131/