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

EN

如果数字是整数- 就地基数排序可以给出O(nlogk)时间，其中k是数字的范围，n是元素的数量。

注意，对于递归调用的堆栈跟踪，该算法需要O(logk)空间。

如果您可以将k绑定到一个常量(例如2^64)--您将得到O(n)空间中的O(1)时间。

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

如果你对数字本身的范围有一个严格的限制，这是可以做到的。

例如，您知道有两个数组A和B，数字绑定在-128和+127之间(8位签名)。您只是拥有一个由256个位置组成的数组。每个数字n将映射到n + 128位置。

在这两个数组上迭代，对于数组A，会增加相应的位置，而对于数组B，则会减少。然后检查所有位置是否为0。如果是，数组就是排列，如果不是，则不是。

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

还请注意，时间复杂度可以进一步降低为简单的O(n)而不是O(n+k)。您只需保持一个运行总数的数字，有非零计数。每次增量/减少将计数推送到其他内容时，都会增加运行的总数。每次它被推到零的时候，你就会减少总数。最后，如果总数为0，则所有计数都为0。

编辑:Amit的答案可能有一个更好的空间复杂性，不过:)

PS:但是，如果数字数组是流进来的，那么这个算法就可以应用，因此它们实际上从来不需要全部保存在内存中。因此，如果条件合适的话，它的空间复杂度可能比直接排序要小。