如何调整数组使得其逆序对的数量为偶数

核心原理 #

交换数组中任意两个相邻元素，逆序对的数量只会增加1或者减少1，因此逆序对的奇偶性必然发生翻转。这个特性不需要对数组做额外复杂计算就能直接利用。

操作步骤 #

• 首先调用已实现的getInvCount(arr)函数，计算当前数组的逆序对总数
• 如果返回值为奇数，仅需要交换数组中任意一对相邻的不相等元素即可，调整后逆序对总数就会变为偶数

优先选择交换数组最后两个元素操作最简单，不需要遍历查找

针对给出的示例验证 #

你提供的示例数组arr = [1, 20, 6, 4, 22 , 5 , 12 , 3]计算得到的逆序对总数为15，属于奇数：

• 交换最后两个相邻元素12和3，得到新数组[1, 20, 6, 4, 22, 5, 3, 12]
• 新数组逆序对总数为14，符合偶数要求

特殊情况处理 #

如果数组最后两个元素相等，交换不会改变逆序对奇偶性，只需要往前找一对不相等的相邻元素交换即可。

内容的提问来源于stack exchange，提问作者Rey