判断两个数组是否具有相同成员的算法

Question

比较两个数组以查看它们是否具有相同成员的最佳算法是什么？

假设没有重复项,成员可以按任何顺序排列,并且两者都没有排序.

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

Answer 1

明显的答案是:

1. 对两个列表进行排序,然后检查每个元素以查看它们是否相同
2. 将一个数组中的项添加到哈希表中,然后遍历另一个数组,检查每个项是否在哈希中
3. nickf的迭代搜索算法

你使用哪一个取决于你是否可以先对列表进行排序,以及是否有一个好的哈希算法.

Answer 2

您可以将一个加载到哈希表中,跟踪它有多少个元素.然后,循环遍历第二个,检查其每个元素是否都在哈希表中,并计算它有多少个元素.如果第二个数组中的每个元素都在哈希表中,并且两个长度匹配,则它们是相同的,否则它们不相同.这应该是O(N).

要在存在重复项的情况下使其工作,请跟踪每个元素的数量.在第一个数组上循环时递增,在第二个数组上循环时递减.在第二个数组的循环期间,如果您在哈希表中找不到某些内容,或者计数器已经为零,则它们是不相等的.还要比较总计数.

在存在重复的情况下工作的另一种方法是对两个数组进行排序并进行线性比较.这应该是O(N*log(N)).

Answer 3

假设你不想打扰原始数组和空间是一个考虑因素,另一个使用比排序两个数组更少空间的O(n.log(n))解决方案是:

1. 如果数组大小不同,则返回FALSE
2. 排序第一个数组--O(n.log(n))时间,所需的额外空间是一个数组的大小
3. 对于第二个数组中的每个元素,使用二进制搜索检查它是否在第一个数组的排序副本中 - O(n.log(n))时间

如果您使用此方法,请使用库例程进行二进制搜索.二进制搜索出乎意料地容易出错.

[在审查建议字典/集合/散列查找的解决方案后添加:]

在实践中我会使用哈希.有几个人已经断言哈希的O(1)行为,导致他们得出一个基于哈希的解决方案是O(N).典型的插入/查找可能接近于O(1),并且一些散列方案保证最坏情况下的O(1)查找,但是在构造散列时最坏情况插入不是O(1).给定任何特定的散列数据结构,会有一些输入会产生病态行为.我怀疑存在散列数据结构,其中最坏情况为[插入N元素然后查找-N元素] O(N.log(N))时间和O(N)空间.

Answer 4

在数组通常不同的情况下，您可以使用签名（对数组成员的交换操作）来进一步优化，o(n log n)从而节省内存分配。签名可以是布隆过滤器的形式，甚至是简单的交换操作，如加法或异或。

一个简单的示例（假设 long 作为签名侧，而 gethashcode 作为良好的对象标识符；如果对象是整数，那么它们的值是更好的标识符；并且某些签名将大于 long）

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;
}