我有一个长度为int[]的N数组，其中包含值0、1、2 ....(N-1)，即它表示整数索引的排列。
确定排列是odt还是parity的最有效方法是什么？
(我特别希望避免在可能的情况下为临时工作空间分配对象...。)
最佳答案
我认为您可以通过简单地计算cycle decomposition在O(n)时间和O(n)空间中做到这一点。
您可以通过简单地从第一个元素开始并遵循路径直到返回起点来计算O(n)中的循环分解。这为您提供了第一个周期。沿着路径将每个节点标记为已访问。
然后重复下一个未访问的节点，直到所有节点都标记为已访问。
长度为k的循环的奇偶性为(k-1)％2，因此您可以简单地将发现的所有循环的奇偶性相加，以找到整体置换的奇偶性。
节省空间
将节点标记为已访问的一种方法是在访问数组时将N添加到数组中的每个值。然后，您将能够进行最后的整理O(n)传递，以将所有数字恢复为原始值。