如何计算数组满足array[i]≠i所需的最少相邻元素交换次数

问题定义 #

给定任意整数数组，计算所需的最少相邻元素交换次数，使得调整后的数组所有位置均满足条件array[i] ≠ i（默认数组下标从0开始）。
参考示例：输入[2, 1, 3]，输出1。

核心思路 #

首先需要识别数组中的「冲突位置」：即满足array[i] == i的下标。冲突位置会以连续块的形式存在，对于长度为m的连续冲突块，每次相邻交换最多可以解决2个冲突，因此处理该块所需的最少交换次数为ceil(m / 2)（即对m除以2向上取整），累加所有冲突块的计算值即可得到最终结果。

实现步骤 #

• 遍历数组，识别所有连续的冲突段，记录每段的长度m
• 对每个冲突段计算ceil(m / 2)，累加到总交换次数中
• 遍历完成后返回总交换次数即可

示例验证 #

输入示例：[2, 1, 3]

1. 遍历数组：下标0值为2≠0，下标1值为1==1（冲突），下标2值为3≠2，得到长度为1的单个冲突段
2. 计算ceil(1/2) = 1，总交换次数为1，和示例输出一致

示例代码（Python） #

import math

def min_adjacent_swaps(arr):
    n = len(arr)
    # 特殊情况：长度为1的数组不可能满足条件
    if n == 1:
        return -1 if arr[0] == 0 else 0
    total = 0
    i = 0
    while i < n:
        # 统计连续冲突段的长度
        if arr[i] == i:
            conflict_len = 0
            while i < n and arr[i] == i:
                conflict_len += 1
                i += 1
            total += math.ceil(conflict_len / 2)
        else:
            i += 1
    return total

# 测试用例
print(min_adjacent_swaps([2,1,3])) # 输出1
print(min_adjacent_swaps([0,1,2,3])) # 输出2
print(min_adjacent_swaps([0,2,1,3])) # 输出2

注意事项 #

• 若题目要求数组下标从1开始计数，仅需将冲突判断条件修改为arr[i] == i+1即可
• 若不存在符合要求的排列（如长度为1且元素为0的数组），可返回-1或其他自定义无解标识

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