比较两个数组或arraylists,找到相似和不同的值

Question

我有两个数组(或更简单的arraylists)字符串.我需要比较这些,找到只存在于第一个数组中的数据,它们存在于两者中,并且只存在于第二个数组中.这些阵列的长度不同,可能的顺序不同.如有必要,我想我可以对它们进行排序......

我知道我可以一起破解这个,但我认为这可能有一个相当标准和有效/"最佳"的解决方案,而且我比任何事情都更好奇.

我正在使用c#,但如果你想用另一种语言编写解决方案,欢迎任何帮助.

谢谢您的帮助!

Answer 1

如果数组很大,那么你将需要使用对这些操作有效的数据结构; 数组不是.

如果阵列的大小为n,那么天真的解决方案是O(n ^ 2).

如果您对数组进行排序,那么您可以二进制搜索它们的项目; 排序可能是O(n lg n)并且每次搜索以ng n为代价搜索n次也将是O(n lg n).

如果将每个数组转换为HashSet<T>第一个,那么可以在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;