两个阵列是否相互排列？

Question

可能重复:
检查数组B是否为A的排列

给出2个未排序的整数数组a并且b大小相等.确定是否b是一个排列a.可以这样在做O(n) time和O(1) space？

我想到的第一个解决方案就是使用XOR,即XOR all the elements of a and b and if the resultant is 0 which means that b is a permutation of a.但他给出了这种方法失败的例子.例如 -

a: [1 6 0 0 4] -- b: [1 0 6 1 5]
a: [1 6 0 0 5] -- b: [1 0 6 1 4]

任何一个有任何想法,如何做到O(n) time和O(1) space？

Answer 1

如果您的集合元素是非负的，并且您有BigInteger可用的无界整数类型（a或类似），您可以在集合上定义一个函数A：

C(A) = product(p_(a+1)))对于每个a在A

其中p_n是n第一个质数。那么C仅取决于中的值A，而不取决于它们的顺序；并且值的任何更改都会发生变化C。

例如，

C([1 6 0 0 4]) = p_2.p_7.p_1.p_1.p_5 = 3.17.2.2.11 = 2244

（显然，任何具有相同元素的集合都具有相同的C，无论顺序如何），并且

C([1 6 0 1 4]) = p_2.p_7.p_1.p_2.p_5 = 3.17.2.3.11 = 3366

所以我们知道这些集合是不同的。这使用了算术基本定理，该定理规定任何大于 1 的整数都可以写成素数的唯一乘积（取决于因子的排序）。或者也许它使用了一个推论。这个方法是我刚想出来的，可能行不通。这篇文章并不是试图证明其正确性......