确定两个数组是否相同排列？

可能重复：
Check if array B is a permutation of A 确定两个数组是否相同排列？

有没有办法告诉如果两个数字阵列（可包含正片，负片或重复）是彼此的排列在O(n)时间复杂度和O(1)空间的复杂性？由于空间有限，我无法解决这个问题。

2012-07-15 Peter

它们是固定长度整数数组吗？ – harold 2012-07-15 08:06:15

如果数字是整数 - in-place radix sort可以给你O(nlogk)时间，其中k是号码的范围，n是元素的数量。
请注意，该算法需要O(logk)空间，用于递归调用的堆栈跟踪。
如果你可以将k限定为一个常数（例如2^64） - 你可以得到O(n)的时间，空间为O(1)。

排序后 - 您可以简单地迭代两个数组，并检查它们是否相同。

来源

2012-07-15 08:09:03 amit

如果您对数字范围本身有严格的限制，那么可以这样做。

举个例子，你知道你有两个数组A和B，数字被绑定在-128和+127之间（8位有符号）。您只需拥有256个位置的阵列。每个号码n将映射到位置n + 128。

您迭代这两个数组，对于数组A，您将增加相应的位置，对于您减小的数组B。然后你检查所有位置是否为0。如果是的话，这些数组就是排列，如果不是的话，它们就不是。

时间复杂度为O(n+k)。空间复杂度为O(k)，其中k是数字的范围。由于k独立于n，所以这就是O(n)和O(1)就n而言，只要你有一个约束k。

还要注意时间复杂度可以进一步简化为O(n)而不是O(n+k)。您只需保持总数不为零的数字。每次增加/减少都会将计数从其他值中推出，从而增加运行总数。每当它将到归零时，就减少总数。最后，如果总为0，则所有计数为0

编辑：Amit的答案很可能有一个更好的空间复杂度虽然:)

PS：不过，这种算法可以当的阵列应用数字流入，所以他们永远不必全部留在记忆中。所以它可能比直接排序的空间复杂度更小如果条件正确

来源

2012-07-15 08:12:25 entropy

使用散列映射而不是固定大小的数组可以使用相同的方法将空间要求降低到'O（min {k，n}）'。 – amit 2012-07-15 08:20:15

是的，两者都是真实的，这只是一个例子。此外，阿米特的建议是这种情况的一般情况。'（add 128）'可以是散列函数本身。所以一般情况下只是使用hashmap。 – entropy 2012-07-15 08:37:30

确定两个数组是否相同排列？

回答

相关问题