比较两个数组或数组列表，找到相似和不同的值

Question

我有两个字符串数组（或者数组列表，如果更容易的话）。我需要比较它们，找到哪些只存在于第一个数组中，哪些同时存在于两个数组中，哪些只存在于第二个数组中。这些数组的长度不同，并且顺序可能不同。如果有必要，我想我可以对它们进行排序......

我知道我可以将它们组合在一起，但我认为这可能有一个相当标准和有效/“最佳”的解决方案，而且我比任何事情都更好奇。

我使用 C# 来实现此目的，但如果您想用其他语言编写解决方案，欢迎提供任何帮助。

感谢您的帮助！

Answer 1

如果数组很大，那么您将需要使用对这些操作有效的数据结构；数组则不然。

如果数组的大小为 n，则简单的解决方案时间复杂度为 O(n^2)。

如果您对数组进行排序，那么您可以对它们进行二分搜索以查找项目；排序可能是 O(n lg n)，并且每次搜索花费 lg n 的成本搜索 n 次，时间也将是 O(n lg n)。

如果您首先将每个数组转换为 HashSet，那么您可以在 O(n) 时间和 O(n) 额外空间内完成此操作。

Answer 2

var onlyinfirst = from s in list1 where !list2.Contains(s) select s;
var onlyinsecond = from s in list2 where !list1.Contains(s) select s;
var onboth = from s in list1 where list2.Contains(s) select s;