5

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

给定 2 个大小相等的a未排序整数数组。b确定是否b是 的排列a。这可以在O(n) timeand中完成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？

4

3 回答 3

2

在整数的有界范围的情况下 - 让该范围可以[n,m]使您可以使用就地基数排序m-n = U对数组进行排序，也在这篇精彩的帖子中进行了讨论。

在你有两个排序数组之后 - 对两者的简单迭代可以给你答案 - 当且仅当排序数组相同时，原始数组是彼此的排列。

注意：
这个答案中有一些“作弊”[因此我没有发布它，直到 OP 在评论中要求它..]，因为它的时间复杂度是O(nlogU)，而空间是O(logU). 然而，对于有界范围——我们可以假设O(logU) = O(1)，对于这些情况，我们得到O(n)时间和O(1)空间。

于 2012-06-07T12:10:20.887 回答
1

您的异或解决方案基本上是基于散列的解决方案，但使用质量较差的散列函数。

你想要的是一个哈希函数......

  1. 给出极不可能发生冲突的哈希值，因此它们可以被视为整数的唯一标识符。Git 使用 SHA-1 哈希来识别源代码版本，冲突的概率非常低，可以忽略不计。

  2. 可交换（如 xor 和 plus）并且可能是关联的，因此项目的顺序不会改变生成的哈希值。

第二个要求可能是尴尬的。我在谷歌呆了一点时间，但只是害怕“准群”之类的词。

于 2012-06-07T12:33:47.380 回答
1

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

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

哪里p_n是第nth 素数。然后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 的整数都可以写成素数的唯一乘积（直到因子的排序）。或者它使用了一个推论。这个方法我刚编出来的，可能行不通。这篇文章并不是试图证明其正确性......

于 2012-06-07T09:44:19.730 回答