求将数组B转为数组A所需的最小相邻交换（Inversion）次数的高效算法

问题本质转化 #

将数组B通过最少相邻交换转化为A的次数，等价于将B按A的元素顺序映射后得到的数组的逆序数。因为每次相邻交换只能消除一个逆序对，所以逆序数就是最少交换次数。

具体步骤 #

1. 建立元素位置映射表
   遍历数组A，用字典记录每个元素在A中的索引位置，时间复杂度O(n)：

   pos_map = {elem: idx for idx, elem in enumerate(A)}
   

2. 生成映射数组
   遍历数组B，将每个元素替换为它在A中的索引，得到数组C，时间复杂度O(n)：

   C = [pos_map[elem] for elem in B]
   

3. 计算数组C的逆序数
   使用归并排序的方法计算逆序数，时间复杂度O(n log n)，这是当前最优的线性对数级解法。

示例验证 #

• 示例a：
  A = ['a', 'b', 'c', 'd', 'e']，pos_map为{'a':0, 'b':1, 'c':2, 'd':3, 'e':4}
  B = ['b', 'e', 'd', 'c', 'a']，映射后C = [1,4,3,2,0]
  逆序数计算：1>0（1次）、4>3/2/0（3次）、3>2/0（2次）、2>0（1次），总计7次，与示例结果一致。

• 示例b：
  A = ['a', 'e', 'c', 'd', 'b']，pos_map为{'a':0, 'e':1, 'c':2, 'd':3, 'b':4}
  B = ['a', 'c', 'e', 'b', 'd']，映射后C = [0,2,1,4,3]
  逆序数为(2,1)和(4,3)，共2次，与示例结果一致。

逆序数计算的实现代码（Python） #

def count_total_inversions(arr):
    def merge_sort_and_count(arr):
        if len(arr) <= 1:
            return arr, 0
        mid = len(arr) // 2
        left, inv_left = merge_sort_and_count(arr[:mid])
        right, inv_right = merge_sort_and_count(arr[mid:])
        merged, inv_merge = merge(left, right)
        return merged, inv_left + inv_right + inv_merge

    def merge(left, right):
        merged = []
        i = j = 0
        inv_count = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
                inv_count += len(left) - i
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged, inv_count

    _, total_inversions = merge_sort_and_count(arr)
    return total_inversions

# 使用示例
A = ['a', 'b', 'c', 'd', 'e']
B = ['b', 'e', 'd', 'c', 'a']
pos_map = {elem: idx for idx, elem in enumerate(A)}
C = [pos_map[elem] for elem in B]
print(count_total_inversions(C))  # 输出7

复杂度分析 #

整个流程的时间复杂度为O(n log n)，其中：

• 映射表构建和数组转换为O(n)
• 归并排序计算逆序数为O(n log n)
  相比原O(n²)的算法，能高效处理大规模输入。

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