比较两个长度相同的整数数组

Question

[描述]给定两个长度相同的整数数组.设计一种能够判断它们是否相同的算法."相同"的定义是,如果这两个数组按排序顺序排列,则相应位置的元素应该相同.

[Example]
<1 2 3 4>  = <3 1 2 4>
<1 2 3 4> != <3 4 1 1>

[限制]算法应该需要恒定的额外空间和O(n)运行时间.

Answer 1

(面试问题可能过于复杂.)

(您可以使用O(N)时间来检查min,max,sum,sumsq等是否相等.)

使用无空间基数排序对两个数组进行就地排序.O(N)时间复杂度,O(1)空间.

然后使用通常的算法比较它们.O(N)时间复杂度,O(1)空间.

(提供的(最大 - 最小)数组是O(N ^k),有限k.)

Answer 2

您可以尝试一种概率方法 - 将数组转换为某个大基数中的数字B，并按某个素数取模P，例如B^a_i对所有imod 一些大数求和P。如果它们的结果相同，请再次尝试获取任意数量的素数。如果任何尝试都是错误的，那么它们就是不正确的。如果他们通过了足够多的挑战，那么他们很有可能是平等的。

B对于> N、 > 最大数字有一个简单的证明P。所以一定存在无法应对的挑战。这实际上是确定性方法，尽管复杂性分析可能更困难，具体取决于人们如何看待输入大小（而不是元素数量）的复杂性。