给定两个具有不同元素的未排序数组A
和B
,确定A
和B
可以重新排列,使它们相同。
我的策略如下:
- 首先,使用O(N) 时间的确定性选择算法找到
A
和Max 的MaxB
的 strong>,如果它们没有相同的 Max,我们可以自动声明它们不相同,否则,移动到第 2 步。 - 将两个数组合并在一起并创建一个大小为 2N 的数组
C
。 - 通过创建大小为 Max(A) 的数组
D
并扫描C
来使用计数排序算法并增加D
中适当索引的计数器 (我们实际上不需要完成计数排序算法,我们只需要这个中间步骤)。 - 扫描
D
数组,如果有D[i] = 1
,我们知道数组不相同,否则它们相同。
声明:时间复杂度为 O(N),并且没有空间限制。
这是一个正确的算法吗?
最佳答案
前面的一个小修正(并删除了一个不必要的步骤):
找到最大值。 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 个字节中的数字是可能的数组大小,并且根据类的不同,这样的哈希函数可能是不可能的。
关于arrays - 确定两个未排序的数组是否相同?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33272926/