可能重复：
检查数组 B 是否是 A 的排列
有没有办法判断两个数字数组（可以包含正数、负数或重复数）在O(n)时间复杂度和O(1)空间复杂度上是否相互排列？由于空间有限，我无法解决它。
问问题
245 次
2 回答
2
如果数字是整数 -就地基数排序可以给你O(nlogk)时间，其中k是数字的范围，n是元素的数量。
请注意，该算法需要O(logk)空间，用于递归调用的堆栈跟踪。
如果您可以绑定k到一个常数（例如 2^64） - 您将获得空间O(n)时间O(1)。
排序后 - 您可以简单地迭代两个数组并检查它们是否相同。
于 2012-07-15T08:09:03.613 回答
0
如果您对数字本身的范围有硬性限制，则可以这样做。
例如，假设您知道您有两个数组 A 和 B，并且这些数字绑定在 -128 和 +127（8 位有符号）之间。您只需拥有 256 个位置的数组。每个数字n都将映射到该位置n + 128。
您遍历两个数组，对于数组 A，您将增加相应的位置，对于数组 B，您将减少。然后检查所有位置是否为 0。如果是，则数组是排列，如果不是，则不是。
时间复杂度为O(n+k)。空间复杂度是O(k)数字k的范围。既然k是独立于 的n，那么这就是O(n)andO(1)就目前n而言，只要你有一个界限k。
另请注意，时间复杂度可以进一步降低到简单地O(n)代替O(n+k). 您只需保留计数非零的数字的运行总数。每次增量/减量将计数从其他事物推入时，您都会增加运行总数。每次它被推到零时，你都会减少总数。最后，如果总数为 0，则所有计数均为 0。
编辑：虽然阿米特的答案可能具有更好的空间复杂度:)
PS：但是，如果数字数组被流入，则可以应用此算法，因此它们实际上不必全部保存在内存中。因此，如果条件正确，它可能比直接排序具有更小的空间复杂度
于 2012-07-15T08:12:25.500 回答