如何通过对每对相邻元素恰好交换一次生成字典序最小排列？

核心分析 #

题目要求每对相邻元素恰好交换一次（即每个相邻位置i和i+1必须执行且仅执行一次交换操作），我们需要选择这些交换的顺序，最终得到字典序最小的排列。

本质上可以通过贪心策略，从左到右逐个确定每个位置的元素：尽可能让当前位置的元素最小，同时保证可以通过未执行的交换操作将该元素移动到当前位置。

具体步骤 #

1. 初始化状态：

   • 复制原数组作为当前操作的数组arr
   • 创建布尔数组swapped（长度为n-1，n为数组长度），标记每个相邻位置是否已完成交换，初始全为false

2. 从左到右遍历每个位置：
   对于每个位置i（从0到n-2）：

   • 找到当前可移动的最远右边界j：从i开始向右，直到遇到第一个已交换的相邻位置，或到达数组末尾。这个范围内的所有相邻位置都未交换过，意味着我们可以将该范围内的任意元素向左移动到i位置。
   • 在arr[i...j]中找到最小元素的最右位置（若有多个相同最小值，选最右边的能为后续位置留出更大调整空间）。
   • 从该最小元素的位置k开始，向左依次执行交换：每次交换arr[m]和arr[m-1]（m从k递减到i+1），同时将swapped[m-1]标记为true（表示这个相邻位置的交换已完成）。

3. 收尾验证：
   按上述步骤执行后，所有相邻交换对都会被恰好执行一次，最终数组即为字典序最小的排列。

示例模拟（数组[5,4,1,3,2]） #

1. 初始状态：arr = [5,4,1,3,2]，swapped = [false, false, false, false]
2. 处理i=0：
   • 最远右边界j=4（所有相邻位置都未交换）
   • arr[0..4]的最小元素是1，位于位置2
   • 交换位置1和2：arr变为[5,1,4,3,2]，标记swapped[1] = true
   • 交换位置0和1：arr变为[1,5,4,3,2]，标记swapped[0] = true
3. 处理i=1：
   • 相邻位置1的swapped[1]已为true，最远右边界j=1（只能保留当前元素5），无需交换
4. 处理i=2：
   • 最远右边界j=4（swapped[2]和swapped[3]都是false）
   • arr[2..4]的最小元素是2，位于位置4
   • 交换位置3和4：arr变为[1,5,4,2,3]，标记swapped[3] = true
   • 交换位置2和3：arr变为[1,5,2,4,3]，标记swapped[2] = true
5. 所有交换完成，最终结果[1,5,2,4,3]符合要求

代码实现（Python） #

def find_min_permutation(arr):
    n = len(arr)
    if n <= 1:
        return arr.copy()
    swapped = [False] * (n - 1)
    arr = arr.copy()
    
    for i in range(n - 1):
        # 找到最远的j，使得从i到j-1的swapped都是False
        j = i
        while j < n - 1 and not swapped[j]:
            j += 1
        # 在arr[i..j]中找最小元素的最右位置
        min_val = arr[i]
        min_pos = i
        for k in range(i, j + 1):
            if arr[k] <= min_val:
                min_val = arr[k]
                min_pos = k
        # 从min_pos向左交换到i
        for m in range(min_pos, i, -1):
            arr[m], arr[m-1] = arr[m-1], arr[m]
            swapped[m-1] = True
    return arr

# 测试示例
original = [5,4,1,3,2]
print(find_min_permutation(original))  # 输出: [1,5,2,4,3]

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