擅长:python、mysql、java
<p>首先在阵列中执行O(n)传递,并计算X、Y和Z。根据计数,我们可以在阵列中定义三个区域:Rx、Ry和Rz。Rx表示数组中X应该位于的索引范围。Ry和Rz也是如此</p>
<p>那么就需要考虑6种排列方式:</p>
<pre><code>Rx Ry Rz
X Y Z no swaps needed
X Z Y 1 swap: YZ
Y X Z 1 swap: XY
Y Z X 2 swaps: XZ and XY
Z X Y 2 swaps: XZ and YZ
Z Y X 1 swap: XZ
</code></pre>
<p>所以,您只需要再进行五次O(n)传递来修复每个可能的排列。从需要1次交换的情况开始。然后修复2个交换案例(如果仍然存在)</p>
<p>例如,用于查找和修复XZY置换的伪代码为:</p>
<pre><code>y = Ry.start
z = Rz.start
while y <= Ry.end && z <= Rz.end
if array[y] == 'Z' && array[z] == 'Y'
array[y] < > array[z]
swapCount++
if array[y] != 'Z'
y++
if array[z] != 'Y'
z++
</code></pre>
<p>每个排列的运行时间为O(n),总运行时间为O(n)</p>
<p>正确性的正式证明留给读者作为练习。我只想指出,案例XZY、YXZ和ZYX以一次交换的成本固定了两个元素(效率2),而案例YZX和ZXY以两次交换的成本固定了三个元素(效率1.5)。因此,首先发现并修复有效案例(并仅在需要时执行无效案例)应该给出最佳答案</p>