Leetcode 31 Next Permutation Python实现数组越界报错求解

错误根源 #

1. pivot查找循环条件顺序错误 #

原代码查找pivot的循环写法为：

while nums[r-1] > nums[r] and r > 0:

Python中and运算符会先执行左侧表达式判断，当r递减到0时，会先尝试访问nums[r-1]，存在索引越界风险。应当将边界判断放在左侧，利用短路特性避免非法访问，修改为：

while r > 0 and nums[r-1] > nums[r]:

2. swap查找循环缺少边界限制 #

pivot右侧的子序列本为降序排列，但当数组存在大量重复元素（如输入[2,2,2]）时，所有元素都等于nums[pivot-1]，原代码的循环：

while nums[pivot-1] >= nums[swap]: # error (line 17)

会让swap一直递减到-1，触发索引越界。需要补充边界条件，保证swap仅在pivot右侧的范围内查找，修改为：

while swap >= pivot and nums[pivot-1] >= nums[swap]:

附加优化（符合题目常数内存要求） #

原代码最后一步使用sorted(nums[pivot:])会生成新的列表，不符合题目要求的常数额外内存限制。由于pivot右侧的子序列本身是降序排列，直接反转即可得到升序序列，修改为：

nums[pivot:] = nums[pivot:][::-1]

修正后完整代码 #

from typing import List
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        # 找pivot
        r = len(nums) - 1
        while r > 0 and nums[r-1] > nums[r]:
            r -= 1
        pivot = r 

        if pivot == 0: 
            nums.sort()
            return 

        # 找swap位置
        swap = len(nums) - 1
        while swap >= pivot and nums[pivot-1] >= nums[swap]:
            swap -= 1
        nums[pivot-1], nums[swap] = nums[swap], nums[pivot-1]

        # 反转pivot右侧序列
        nums[pivot:]  = nums[pivot:][::-1]

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