比较两个数组是否相同的最快方法是什么?
我有两个对象数组,它们可能具有相同的值,但顺序不同,例如
{ "cat", "dog", "mouse", "pangolin" } { "dog", "pangolin", "cat", "mouse" }
我希望将这两个数组视为相等。 测试这个的最快方法是什么?
我不能保证这是最快的 ,但它肯定非常有效:
bool areEquivalent = array1.Length == array2.Length && new HashSet(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();
我认为唯一合理的方法是对它们进行排序然后进行比较。
排序需要O(n logn)
并比较O(n)
,因此仍然是O(n logn)
的总和
你尝试过类似的东西吗?
string[] arr1 = {"cat", "dog", "mouse", "pangolin"}; string[] arr2 = {"dog", "pangolin", "cat", "mouse"}; bool equal = arr1.Except(arr2).Count() == 0 && arr2.Except(arr1).Count() == 0;
将两个数组转换为HashSet并使用setequals
我会使用HashSet,假设没有重复
string[] arr1 = new string[] { "cat", "dog", "mouse", "pangolin" }; string[] arr2 = new string[] { "dog", "pangolin", "cat", "mouse" }; bool result = true; if (arr1.Length != arr2.Length) { result = false; } else { HashSet hash1 = new HashSet (arr1); foreach (var s in arr2) { if (!hash1.Contains(s)) result = false; } }
编辑:
如果你只有四个元素,跳过HashSet并在比较中使用arr1.Contains可能会更快。 为您的arrays大小测量和选择最快。
伪代码:
A:array B:array C:hashtable if A.length != B.length then return false; foreach objA in A { H = objA; if H is not found in C.Keys then C.add(H as key,1 as initial value); else C.Val[H as key]++; } foreach objB in B { H = objB; if H is not found in C.Keys then return false; else C.Val[H as key]--; } if(C contains non-zero value) return false; else return true;