求提升数组有序值的最长交换序列长度

核心分析 #

要计算最长交换序列长度，关键在于利用置换循环分解：

• 只有交换同一循环内的错位元素，才能提升有序值。
• 每个长度为k的循环，最多贡献k-1次有效交换（每次交换都严格提升有序值）。
• 总最长序列长度 = 错位元素总数 - 循环数量。

详细步骤 #

1. 生成排序数组：将原数组a排序得到b，b是a的非降序版本。
2. 标记错位元素：创建布尔数组mask，mask[i] = true当且仅当a[i] != b[i]（即该位置元素不在正确位置）。
3. 构建值到错位索引的映射：用字典val_to_indices，键为元素值，值为存储该值的所有错位索引的队列（保证顺序匹配，避免重复元素导致的循环分解错误）。
4. 循环分解：遍历所有索引，对未访问的错位元素，追踪其所在的循环：
   • 每找到一个新循环，循环计数t加1。
   • 遍历循环内所有元素，标记为已访问，并通过val_to_indices找到下一个循环节点（即当前位置应放置元素的原错位索引）。
5. 计算结果：最长序列长度 = 错位元素总数m（即sum(mask)） - 循环数量t。

伪代码 #

def longest_swap_sequence(a):
    n = len(a)
    b = sorted(a)
    mask = [a[i] != b[i] for i in range(n)]
    m = sum(mask)
    if m == 0:
        return 0  # 数组已完全有序，无需交换
    
    from collections import defaultdict, deque
    val_to_indices = defaultdict(deque)
    for i in range(n):
        if mask[i]:
            val_to_indices[a[i]].append(i)
    
    visited = [False] * n
    cycle_count = 0
    
    for i in range(n):
        if not visited[i] and mask[i]:
            cycle_count += 1
            j = i
            while not visited[j] and mask[j]:
                visited[j] = True
                # 获取当前位置j需要匹配的值，找到对应的错位索引
                target_val = b[j]
                j = val_to_indices[target_val].popleft()
    
    return m - cycle_count

关键说明 #

• 重复元素处理：通过队列存储错位索引，保证每个值的索引按原数组顺序匹配，避免将正确位置的元素误加入循环。
• 时间效率：排序操作占O(n log n)，其余步骤均为线性时间O(n)，整体复杂度完全适配3×10^5规模的数组。
• 正确性：每个循环内的交换都能保证有序值严格提升，且序列长度最大化（每个循环贡献k-1步，无无效交换）。

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