我试图找到一个解决的办法，但也没有得到多少我的头了。

I tried to find a solution to this but couldn't get much out of my head.

我们都提供两个未排序整数数组A和B.我们要检查数组B是否是A的置换如何才能做到这一点？即使异或数字不会工作，因为可以有几个反例具有相同的XOR值BT是不是彼此的排列。

We are given two unsorted integer arrays A and B. We have to check whether array B is a permutation of A. How can this be done.? Even XORing the numbers wont work as there can be several counterexamples which have same XOR value bt are not permutation of each other.

一个解决方案需要O（n）的时间和空间O（1）

A solution needs to be O(n) time and with space O(1)

任何帮助是值得欢迎的！ 谢谢你。

Any help is welcome!! Thanks.

推荐答案

现在的问题是理论上的，但你可以在O做到这一点（n）时间及O（1）空间。分配的2 32 计数器的阵列，并将它们全部设置为零。这是O（1）的步骤，因为该阵列具有恒定大小。然后通过两个数组迭代。对于数组A，增加相应的读取整数计数器。对于数组B，递减他们。如果数组b迭代过程中遇到了消极的计数值，停止---数组不是彼此的排列。否则在端（假设A和B具有相同的尺寸，一个prerequisite）的计数器阵列是全零和两个数组彼此的排列。

The question is theoretical but you can do it in O(n) time and o(1) space. Allocate an array of 232 counters and set them all to zero. This is O(1) step because the array has constant size. Then iterate through the two arrays. For array A, increment the counters corresponding to the integers read. For array B, decrement them. If you run into a negative counter value during iteration of array B, stop --- the arrays are not permutations of each others. Otherwise at the end (assuming A and B have the same size, a prerequisite) the counter array is all zero and the two arrays are permutations of each other.

这是O（1）空间和O（n）时间的解决方案。然而，它是不实际的，但很容易通过作为解决该问题访谈。至少它应该的。

This is O(1) space and O(n) time solution. However it is not practical, but would easily pass as a solution to the interview question. At least it should.

使用的不确定性的的模型计算，检查两个数组的不可以每个人的排列可以在O（1）空间完成的，O（ n）的通过猜测已不同的两个阵列的计数，然后计数在两个阵列的该元素的实例的元素时间

Using a nondeterministic model of computation, checking that the two arrays are not permutations of each others can be done in O(1) space, O(n) time by guessing an element that has differing count on the two arrays, and then counting the instances of that element on both of the arrays.

在随机的计算模型，构造一个随机交换散列函数，并计算哈希值的两个数组。如果散列值不同时，数组不是彼此的排列。否则，他们可能是。重复多次，使低于期望的阈值误差的概率。同样在O（1）空间O（n）时间的方法，但随机的。

In randomized model of computation, construct a random commutative hash function and calculate the hash values for the two arrays. If the hash values differ, the arrays are not permutations of each others. Otherwise they might be. Repeat many times to bring the probability of error below desired threshold. Also on O(1) space O(n) time approach, but randomized.

在并行的计算模型，让'N'是输入数组的大小。分配'N'线程。每个线程I = 1 ... N读取从第一阵列的第i号;让这为x。然后在同一线程计数事件x中的第一阵列中的数量，然后检查所述第二阵列上相同的计数。每一个线程使用O（1）空间和O（n）的时间。

In parallel computation model, let 'n' be the size of the input array. Allocate 'n' threads. Every thread i = 1 .. n reads the ith number from the first array; let that be x. Then the same thread counts the number of occurrences of x in the first array, and then check for the same count on the second array. Every single thread uses O(1) space and O(n) time.

国米preT整数数组[A1，...，一]多项式x A1 + X A2 + ... + X 的其中x是自由变量，并检查数值为获得两个多项式的等价性。使用浮点算术为O（1）空间和O（n）的时间操作。由于舍入误差，并因为等价数值检查不是一门精确的方法是概率性的。可替代地，除$ P $角多项式在整数模素数，并执行相同的概率检查

Interpret an integer array [ a1, ..., an ] as polynomial xa1 + xa2 + ... + xan where x is a free variable and the check numerically for the equivalence of the two polynomials obtained. Use floating point arithmetics for O(1) space and O(n) time operation. Not an exact method because of rounding errors and because numerical checking for equivalence is probabilistic. Alternatively, interpret the polynomial over integers modulo a prime number, and perform the same probabilistic check.