什么是比较两个数组是否具有相同成员的最佳算法?
假设没有重复项,成员可以在任何顺序中,并且都没有排序。
compare(
[a, b, c, d],
[b, a, d, c]
) ==> true
compare(
[a, b, e],
[a, b, c]
) ==> false
compare(
[a, b, c],
[a, b]
) ==> false
什么是比较两个数组是否具有相同成员的最佳算法?
假设没有重复项,成员可以在任何顺序中,并且都没有排序。
compare(
[a, b, c, d],
[b, a, d, c]
) ==> true
compare(
[a, b, e],
[a, b, c]
) ==> false
compare(
[a, b, c],
[a, b]
) ==> false
显而易见的答案有:
你要使用哪个取决于您是否可以先对列表进行排序,以及您是否有一个好的哈希算法可用。
o(n log n)
或内存分配。
签名可以采用布隆过滤器或甚至是简单的可交换操作(如加法或异或)的形式。public bool MatchArrays(object[] array1, object[] array2)
{
if (array1.length != array2.length)
return false;
long signature1 = 0;
long signature2 = 0;
for (i=0;i<array1.length;i++) {
signature1=CommutativeOperation(signature1,array1[i].getHashCode());
signature2=CommutativeOperation(signature2,array2[i].getHashCode());
}
if (signature1 != signature2)
return false;
return MatchArraysTheLongWay(array1, array2);
}
使用加法操作(如果需要,可以使用其他交换操作,如布隆过滤器)来确定位置
public long CommutativeOperation(long oldValue, long newElement) {
return oldValue + newElement;
}
public static bool ArrayEqual(int[] list1, int[] list2)
{
if (list1 == null || list2 == null)
{
throw new Exception("Invalid input");
}
if (list1.Length != list2.Length)
{
return false;
}
int diff = 0;
for (int i = 0; i < list1.Length; i++)
{
diff += list1[i] - list2[i];
}
return (diff == 0);
}
4完全不工作,它是最糟糕的
diff += Math.abs(list1[i]) - Math.abs(list2[i]);
- Buhake Sindiabs
不会奏效。考虑情况:[2, 4, 0] 和 [5, 1, 0] => diff[-3, 3, 0] == 0。 - Vasu如果数组的元素是不同的,则对两个数组的所有元素进行异或(按位异或),如果答案为零,则两个数组具有相同的数字集。时间复杂度为O(n)。
{1, 2, 3, 3}
和{1, 2}
中的所有元素执行XOR操作将得到0,但是这两个数组是不同的。 :) - Konstantin Yovkov伪代码:
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;
显然,“最好”的解决方案取决于你的约束条件。如果数据集很小,排序、哈希或暴力比较(如nickf所发表的)都会非常相似。因为你知道你正在处理整数值,所以可以获得O(n)的排序时间(例如基数排序),哈希表也将使用O(n)的时间。像往常一样,每种方法都有缺点:如果想节省空间,排序要么需要你复制数据,要么破坏性地对数组进行排序(丢失当前排序),哈希表显然会有内存开销来创建哈希表。如果你使用nickf的方法,可以几乎不需要任何内存开销,但你必须处理O(n2)的运行时间。你可以选择最适合你目的的方法。