判断两个数组是否有相同元素的算法

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

- nickf

---

为什么不加把劲，看看如果我们不能排序会发生什么。显然，我们需要能够进行相等比较。 - Hugo

听起来你是在问如何比较集合。 - naumcho

Answer 1

显而易见的答案有：

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

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

- Mark Bessey

---

小优化...

1. 如下所述，首先检查长度。2. Java的Set.add(E o)操作返回true，如果元素被添加，则迭代可以简单地测试'if (!setA.add(elementFromB))'并返回false。

- Ken Gentle

哈希表方法的问题在于，当列表中存在重复值时，它无法正常工作。例如，a[1, 2, 2, 3] == b[1, 2, 3, 3]吗？虽然两个列表长度相同，但是b中的所有项都可以在a的哈希表中找到。因此，你需要一个计数项的集合结构，并检查计数是否相等。 - jmucchiello

从数学角度来看，一个集合中不会重复包含相同的值。 - Bob Jansen

方法2比1慢（如果n足够大）：方法2需要O(n^2)次检查，而比较排序可以降至O(n*log(n))。 - 12431234123412341234123

Answer 2

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

为了在重复项存在的情况下使其工作，请跟踪已看到每个元素的数量。在循环遍历第一个数组时增加，在循环遍历第二个数组时减少。在第二个数组的循环过程中，如果在哈希表中找不到某个元素，或者计数器已经为零，则它们不相等。还要比较总计数。

另一种在存在重复项的情况下可行的方法是对两个数组进行排序并进行线性比较。这应该是O（N * log（N））。

- Glomek

Answer 3

您可以使用签名（数组成员的可交换操作）来进一步优化这个问题，特别是当数组通常不同的情况下，可以节省 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;
}

- Yaniv

Answer 4

假设您不想改变原始数组并且空间是一个问题，另一个使用比对两个数组排序更少的空间的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)。

- Frentos

---

如果我们假设数据不具有敌意，最坏情况的时间很少是有趣的。大家都说快速排序的时间复杂度是O(n*log(n))，但它的最坏情况性能是O(n^2)。 - erikkallen

Frentos，你的第一种方法对这个输入不起作用： 数组1 = [1,2,3] 数组2 = [1,1,1] - user674669

Answer 5

这可以用不同的方法来完���：

1-暴力破解：对于数组1中的每个元素，检查它是否存在于数组2中。请注意，这需要记录位置/索引，以便可以正确处理重复项。这需要O（n²）的复杂代码，根本不要考虑...

2-排序两个列表，然后检查每个元素是否相同。排序的时间复杂度为O（n log n），检查的时间复杂度为O（n），因此基本上是O（n log n）。如果不会破坏数组，则可以原地进行排序，否则需要具有2n大小的内存来复制已排序的列表。

3-将一个数组的项和计数添加到哈希表中，然后遍历另一个数组，检查每个项是否在哈希表中，在这种情况下，如果计数不为零，则将其减少，否则从哈希表中删除。创建哈希表需要O（n），在哈希表中检查其他数组项需要O（n），因此为O（n）。这引入了一个最多包含n个元素的哈希表。

4-最佳之选（上述方法中的最佳之选）：从两个数组中相同索引的每个元素中减去或取差值，最后将减去的值相加。例如A1={1,2,3}，A2={3,1,2}，Diff={-2,1,1}，现在将Diff相加=0，这意味着它们具有相同的整数集。这种方法不需要额外的内存，时间复杂度为O（n）。C#代码如下：

    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完全不工作，它是最糟糕的

- goit

---

对于输入[2,4,6]和[-2,8,6]无法通过，输出diff [4，-4，0] = 0。 - nickf

相反，应该这样做：diff += Math.abs(list1[i]) - Math.abs(list2[i]); - Buhake Sindi

abs 不会奏效。考虑情况：[2, 4, 0] 和 [5, 1, 0] => diff[-3, 3, 0] == 0。 - Vasu

在 abs [1,2,3] 和 [-1,2,3] 的情况下，差分值为0是不正确的。因此，我的建议是进行两个差分计算，一个用于正数，另一个用于负数。两个差分值都应该为0。 - Amandeep Kamboj

Answer 6

如果数组的元素是不同的，则对两个数组的所有元素进行异或（按位异或），如果答案为零，则两个数组具有相同的数字集。时间复杂度为O(n)。

- akashrajkn

---

不完全是这样。对于{1, 2, 3, 3}和{1, 2}中的所有元素执行XOR操作将得到0，但是这两个数组是不同的。 :) - Konstantin Yovkov

@KonstantinYovkov，我考虑了那种情况。这就是为什么我写了“如果数组的元素是不同的”。 - akashrajkn

Answer 7

伪代码：

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;

- Mohammad Mazaz

Answer 8

我建议先对两个数组进行排序，然后再进行比较。你可以先比较每个数组的第一个元素，然后是第二个元素，以此类推。

如果发现不匹配，就可以停止比较了。

- Vincent Ramdhanie

Answer 9

如果您先对这两个数组进行排序，那么时间复杂度将为O(N log(N))。

- albertb

Answer 10

显然，“最好”的解决方案取决于你的约束条件。如果数据集很小，排序、哈希或暴力比较（如nickf所发表的）都会非常相似。因为你知道你正在处理整数值，所以可以获得O(n)的排序时间（例如基数排序），哈希表也将使用O(n)的时间。像往常一样，每种方法都有缺点：如果想节省空间，排序要么需要你复制数据，要么破坏性地对数组进行排序（丢失当前排序），哈希表显然会有内存开销来创建哈希表。如果你使用nickf的方法，可以几乎不需要任何内存开销，但你必须处理O(n²)的运行时间。你可以选择最适合你目的的方法。

- Jimmy

---

然而，nickf的解决方案是最容易进行多线程处理的；它不会对共享数据进行任何写操作，并且可以（接近）线性扩展。正如评论中提到的那样，它只有在重复项方面存在问题。 - Jasper Bekkers