<分区>
Possible Duplicate:
Check if array B is a permutation of A
给定 2 个大小相等的未排序整数数组 a 和 b。确定 b 是否是 a 的排列。这可以在 O(n) 时间 和 O(1) 空间 内完成吗？
我想到的第一个解决方案是使用 XOR，即 XOR a 和 b 的所有元素，如果结果为 0，则意味着 b 是一个。但他给出了这种方法失败的例子。例如 -
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) 时间 和 O(1) 空间 内完成吗？
最佳答案
在整数有界范围的情况下 - 让该范围为 [n,m] 这样 m-n = U 您可以使用 in place radix sort 对数组进行排序，也在 this great post 中讨论.
在你有两个排序数组之后 - 对两者进行简单的迭代就可以给你答案 - 当且仅当排序数组相同时，原始数组是彼此的排列。
注意:
这个答案中有一些“作弊”[因此我没有发布它直到 OP 在评论中要求它..]，因为它的时间复杂度是 O(nlogU) ，空间为 O(logU)。但是，对于有界范围 - 我们可以假设 O(logU) = O(1)，对于这些情况，我们得到 O(n) 时间和 O( 1) 空格。
关于algorithm - 两个数组是相互排列的吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10929185/