Python求解k次交换最大排列时列表交换未生效输出错误

核心错误原因 #

你的代码交换未生效的核心问题出在多重赋值时左侧下标引用的计算时机错误：
Python 执行多变量赋值的逻辑是：

1. 先完整计算等号右侧所有表达式，得到值元组
2. 再按从左到右的顺序，依次把值赋给左侧的引用位置

你当前的写法把索引计算写在了左侧的下标位置，导致第二个下标是在第一个赋值操作完成后才计算的，此时数组已经被修改，arr.index(max(arr[i:])) 会返回错误的位置。

以你给出的测试用例k=1，arr=[4,2,3,5,1]为例，执行逻辑如下：

• 第一步计算右侧值：arr[arr.index(max(arr[0:]))]是arr[3] = 5，arr[0] =4，右侧值元组为(5,4)
• 第二步给左侧第一个位置赋值：arr[0] =5，此时数组变为[5,2,3,5,1]
• 第三步计算左侧第二个位置的下标：arr.index(max(arr[0:]))，此时数组第一个元素已经是5，返回下标0
• 第四步给左侧第二个位置赋值：arr[0] =4，数组被改回初始状态，看起来就像交换没有生效

修复方案 #

先提前计算出待交换的最大值下标，再执行交换即可，修改后的代码如下：

def largestPermutation(k, arr):
    n = len(arr)
    # 最多交换n次就能得到完全逆序的最大排列，超过n次取n即可
    k = min(k, n)
    for i in range(k):
        # 提前计算最大值的下标，避免在赋值时重复计算导致索引错误
        max_val = max(arr[i:])
        pos = arr.index(max_val)
        # 如果当前位置已经是最大值，不需要交换，节省交换次数
        if pos == i:
            k +=1
            continue
        arr[i], arr[pos] = arr[pos], arr[i]
    return arr

a =[4,2,3,5,1]
print(largestPermutation(1,a)) # 输出 [5,2,3,4,1]

优化建议 #

当前实现每次调用max和index都是O(n)复杂度，面对大数据量测试用例会超时，可以提前用哈希表存储每个值对应的下标，每次交换后更新下标位置，把时间复杂度降到O(n)。

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