时间戳

首页 > 解决方案 > Leetcode 31. 下一个排列 - Python

python - Leetcode 31. 下一个排列 - Python

问题描述

我正在尝试解决一个 Leetcode 问题：

实现下一个排列，它将数字重新排列为按字典顺序排列的下一个更大的数字排列。如果这样的排列是不可能的，它必须将其重新排列为尽可能低的顺序（即按升序排序）。替换必须就位并且仅使用恒定的额外内存。

我不明白为什么我在第 17 行收到错误消息“列表索引超出范围”（我标记为“错误”）。测试用例都在工作。

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

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

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

            # reverse
            nums[pivot:]  = sorted(nums[pivot:])

标签： pythonalgorithm

解决方案

直接的问题是，对于像这样的输入，它swap可以变得小于，以防止这种变化：0[1, 1]

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

到：

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

此外，您还希望使用>=而不是>在您的枢轴计算循环中，这样，当两个相邻元素相同（例如，）时，您不会过早退出循环，[2, 1, 1]即更改：

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

到：

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

推荐阅读