比较两个数组是否相等的最快方法是什么？
比较两个数组是否相等的最快方法是什么？
提问于 2010-11-11 17:50:58
我有两个对象数组，它们可能具有相同的值，但顺序不同，例如
{ "cat", "dog", "mouse", "pangolin" }
{ "dog", "pangolin", "cat", "mouse" }我希望将这两个数组同等对待。测试它的最快方法是什么？
回答 6
Stack Overflow用户
回答已采纳
发布于 2010-11-11 17:55:00
我不能保证这是最快的，但它肯定是相当有效的：
bool areEquivalent = array1.Length == array2.Length
&& new HashSet<string>(array1).SetEquals(array2);编辑: SaeedAlg和Sandris就不同的重复频率提出了有效的观点，这些重复导致了这种方法的问题。如果这一点很重要，我可以看到两个变通方法(没有过多考虑它们各自的效率)：
1.对数组进行排序，然后按顺序进行比较。从理论上讲，这种方法在最坏的情况下应该具有二次复杂度。例如：
return array1.Length == array2.Length
&& array1.OrderBy(s => s).SequenceEqual(array2.OrderBy(s => s));2.建立每个数组中字符串的频率表，然后进行比较。例如：
if(array1.Length != array2.Length)
return false;
var f1 = array1.GroupBy(s => s)
.Select(group => new {group.Key, Count = group.Count() });
var f2 = array2.GroupBy(s => s)
.Select(group => new {group.Key, Count = group.Count() });
return !f1.Except(f2).Any();Stack Overflow用户
发布于 2010-11-11 17:55:55
我认为唯一合理的方法是对它们进行排序，然后进行比较。
排序需要O(n logn)和比较O(n)，所以这仍然是O(n logn)的总数
Stack Overflow用户
发布于 2010-11-11 17:56:29
你试过像这样的东西吗？
string[] arr1 = {"cat", "dog", "mouse", "pangolin"};
string[] arr2 = {"dog", "pangolin", "cat", "mouse"};
bool equal = arr1.Except(arr2).Count() == 0 && arr2.Except(arr1).Count() == 0;页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4153120
复制相关文章
相似问题
腾讯云开发者
