有效地确定排列的奇偶性

我认为您可以通过简单地计算循环分解在O（n）时间和O（n）空间中做到这一点。

您可以通过简单地从第一个元素开始并遵循路径直到返回起点来计算O（n）中的循环分解。这为您提供了第一个周期。沿着路径将每个节点标记为已访问。

然后重复下一个未访问的节点，直到所有节点都标记为已访问。

长度为k的循环的奇偶校验为（k-1）％2，因此您可以简单地将发现的所有循环的奇偶校验加起来，以找到整体置换的奇偶校验。

节省空间

将节点标记为已访问的一种方法是在访问数组时将N添加到数组中的每个值。然后，您将能够进行最后的整理O（n）传递，以将所有数字恢复为原始值。