algorithm - 检查是否可以使用给定操作对排列进行排序

Question

我有以下问题:
我的任务是确定是否可以对给定的排列进行排序，但只使用一种类型的操作:我们可以将第 i 个元素向左移动两个位置。同样，元素 i-1 和 i-2 向右移动一个位置。

例如: 可以对排列 (2,5,3,4,1) 进行排序，但我们不能对排列 (2,3,5,4,1) 进行排序。

(2,5,3,4,1)
(2,4,5,3,1)
(2,3,4,5,1)
(2,3,1,4,5)
(1,2,3,4,5)

复杂度应该是线性的。 我想出了二次解，但它太慢了。我尝试了贪心法，但失败了。

这个问题让我完全卡住了。

Answer 1

如果有偶数次反转，则可以仅使用此操作对排列进行排序。您可以在 O(n log n) 中使用合并排序来计算倒置。