确定两个未排序的数组是否相同？

Question

给定两个元素不同的未排序数组A和B，确定是否可以重新排列A和B，使它们相等。

我的策略如下：

1.首先使用O(N)时间的确定性选择算法来找到A的最大值和B的最大值。如果它们的最大值不同，我们可以自动声明它们不相同；否则，进入步骤2。

2.将两个数组合并在一起，创建一个大小为2N的数组C。

3.使用计数排序算法，通过创建一个大小为Max(A)的数组D并扫描C并提高适当索引的计数器（我们不需要完整地完成计数排序算法，我们只需要这个中间步骤）。

4.扫描D数组，如果任何D[i] = 1，则我们知道这些数组不相等，否则它们相等。

声明：时间复杂度为O(N)，空间没有限制。

这是一个正确的算法吗？

- Mutating Algorithm

---

@user2357112 我猜 OP 的意思是如果这些数组包含相同的元素，不一定是按相同的顺序。 - deviantfan

@user2357112 这两个数组是无序的，我们想知道是否可以重新排列它们使它们完全相同。 - Mutating Algorithm

@MutatingAlgorithm 这个算法听起来是正确的，但由于它的内存使用情况并不是很实用。此外，对于非整数数组，您还需要解决如何将元素映射到整数的问题。 - deviantfan

如果您可以使用计数排序，只需在两个数组上使用计数排序，然后比较结果即可。 - n. m.

@dwoz 叹气。如果对每个元素进行异或运算...结果也无关紧要，因为有无限个不同的数组具有相同的异或值。在发布一堆无意义的话（这里和下面）之前，请先了解更多关于哈希的知识。 - deviantfan

Answer 1

有个小修改（和一个不必要的步骤的删除）：

找到 A 和 B 中的最大元素。如果不相等，退出。
创建一个大小为 max(A) 的整数数组 C，并将所有元素设置为 0。
迭代 A 中的每个元素 a 并将 C[a] 增加 1。
迭代 B 中的每个元素 b 并将 C[b] 减少 1。
检查 C 是否至少有一个非零值；如果是，则 A 和 B 没有相同的元素。

注意：
a）不需要创建合并的数组。
b）对于两个数组进行递增并检查计数器是否为 1 或 2，如果某个值出现多次，则失败。
c）对于两个数组进行递增并检查计数器是否为奇数，如果某个值在 A 中出现两次且在 B 中未出现，则失败。因此，递增一次，递减一次，并检查是否为 0。

现在，如果最大元素足够小，C 可以放入内存，则它适用于整数数组。

如果 A 和 B 中有大的 64 位值，则无法使用。如果 A 和 B 是双精度数组，则也无法使用（您可以将字节转换为 int 表示，但会再次出现大值）。

如果 A 和 B 是类对象数组，则通常无法使用。您需要一个无冲突哈希，其哈希值最大为 4 字节，以便在这 4 字节中的数字是可能的数组大小，并且根据类别，此类哈希函数可能不可行。

- deviantfan

---

可以使用哈希映射代替计数器数组来克服一些限制。 - Henry

@Henry 如果我必须提出一个明智的建议，我会从一开始就对两个数组进行排序，然后进行比较 :) 是的，哈希映射有助于当前的方法，但我所做的只是纠正 OP 的算法，使其正确工作，而不改变太多。 - deviantfan

Answer 2

解决这个任务的惯用方式是将第一个数组的元素添加到哈希表中。然后迭代第二个数组并检查每个元素是否存在于哈希表中。

哈希表具有分摊插入和搜索时间O(1)(使用足够好的哈希时)，因此整体算法将在O(N)时间内运行，并消耗O(N)附加空间。

这种方法适用于所有元素类型（不仅仅是小整数，如计数排序所需）。但是，如果您的元素是小整数，则可以将哈希表替换为普通布尔数组。

此外，如果数组的元素不是唯一的，则可以通过以计数器作为哈希表中的值来修改此算法。

- Aivean

---

一个哈希表对象查找是我能想象到的最昂贵的方法。 - dwoz

这仅适用于没有重复项的情况。对于一般解决方案，您需要一个计数的哈希表。使用第一个数组对它们进行增量。对于第二个数组，进行减量并在计数为零时删除。然后验证表是否为空。 - Gene

@Gene Aivean 已经说过，它必须被修改才能处理非不同元素。 - deviantfan

Answer 3

O(n) 组件的问题意味着我们正在回答某人的作业问题。在现实世界的计算中，这并不重要（大多数情况下）。

为什么不先查看 Array[].length() 是否相同？

然后，编写一个哈希函数，无论顺序如何都会产生相同的值。（即对每个/所有项进行异或）。在大多数计算语言中，比较哈希的结果应该与 equals 一致。

- dwoz

---

哈希函数不能保证相等性。在现实世界中，比较两个数组是非常常见的任务。一个例子是在单元测试中断言方法调用的结果。然而，在现实世界中有内置工具可以实现这一点，比如HashSet。 - Aivean

“O(n)问题的组成部分意味着我们正在回答某人的家庭作业问题。在现实世界的计算中，没有人关心这个问题（大多数情况下）。但上周我确实关心了一个与家庭作业无关的400GB数组。” - deviantfan

...而且你的编辑是毫无意义的。a）哈希算法与编程语言是不同的。b）按定义，哈希算法生成哈希值，而哈希值并非无冲突的。这与相等是不同的。 - deviantfan

编程的“领域”超出学校范畴了吗？是的。而且我向你保证，如果某个程序运行一小时或一百年对老板来说是很重要的。不是所有的东西都是Facebook、iPhone应用之类的。 （即使Facebook也需要高性能的后台软件）。复杂性确实很重要。 - deviantfan

@dwoz 没有必要再与你争论下去了。请先阅读手册，然后再回来。 - Aivean