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

Question

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

我的策略如下:

1. 首先，使用O(N) 时间的确定性选择算法找到A 和Max 的Max B 的 strong>，如果它们没有相同的 Max，我们可以自动声明它们不相同，否则，移动到第 2 步。
2. 将两个数组合并在一起并创建一个大小为 2N 的数组 C。
3. 通过创建大小为 Max(A) 的数组 D 并扫描 C 来使用计数排序算法并增加 D 中适当索引的计数器 (我们实际上不需要完成计数排序算法，我们只需要这个中间步骤)。
4. 扫描D数组，如果有D[i] = 1，我们知道数组不相同，否则它们相同。

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

这是一个正确的算法吗？

Answer 1

前面的一个小修正(并删除了一个不必要的步骤):

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

注意事项:
a) 无需合并数组。
b) 递增两个数组并检查
如果某个值多次出现，则计数器为 1 或 2 时失败。
c)增加两个数组并检查计数器是否为奇数失败，例如。如果一些
值在 A 中是两倍，在 B 中是 0 次。所以 1x 递增，1x 递减，并检查 0。

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

如果 A 和 B 中有较大的 64 位值，则无法正常工作。如果A和B是例如。双数组，它也不会工作。 (您可以将 byte 转换为 int 表示，但又会出现大值。)

如果 A 和 B 是类对象的数组，它就不起作用(通常)。您将需要一个哈希值为最大值的无冲突哈希。例如。 4 个字节，因此这 4 个字节中的数字是可能的数组大小，并且根据类的不同，这样的哈希函数可能是不可能的。