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