给定两个unsorted arrays A and B具有不同的元素，确定是否A and B可以重新排列，使它们相同。
我的策略如下：
- 首先，使用确定性选择算法O(N)是时候找到Max of
A and Max of B，如果他们没有相同的Max，我们可以自动声明它们是not相同，否则转至步骤 2。
- 将两个数组合并在一起并创建一个数组
C尺寸的2N.
- Use the 计数排序算法通过创建一个数组
D尺寸的Max(A)和扫描C并碰撞适当索引的计数器D （我们实际上不需要完成计数排序算法，我们只需要这个中间步骤）.
- 扫描
D数组，如果有的话D[i] = 1，我们知道数组不相同，否则它们是相同的。
Claim:时间复杂度 O(N)，以及no空间的限制。
这是正确的算法吗？
前面的一个小修正（并删除不必要的步骤）：
找到最大值。 A 和 B 的元素。如果不相等，则退出。
创建一个大小为 max(A) 的整数数组 C，并将所有元素设置为 0。
迭代 A 的每个元素 a 并递增 C[a]。
迭代 B 的每个元素 b 并递减 (!) C[b]。
检查C是否至少有一个非零值；如果是，则 A 和 B 具有不同的元素。
Notes:
a) 无需创建合并数组。
b) 增加两个数组并检查
如果计数器为 1 或 2，则如果某个值多次出现，则失败。
c) 增加两个数组并检查计数器是否为奇数失败，例如。如果有一些
值在 A 中是两倍，在 B 中是 0 倍。因此增加 1 倍，减少 1 倍，并检查是否为 0。
现在它适用于整数数组（如果最大值）。 element 足够小，C 可以容纳在内存中。
如果A和B中有很大的64位值，则不起作用。如果A和B是例如。双数组，它也不起作用。 （您可以将字节转换为 int 表示形式，但又会出现较大的值。）
如果 A 和 B 是类对象的数组，则它不起作用（通常）。您需要一个散列值为 max 的无冲突散列。例如。 4 个字节，因此这 4 个字节中的数字是可能的数组大小，并且根据类的不同，此类哈希函数可能无法实现。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
