leetcode 31. 下一个排列 python

题目描述：

题解：

此题的关键是：下一个更大的排列

如果输入的数组按照降序排列，则当前数组已经是最大的排列，比如[5,4,3,2,1]

如果输入数组不是完全降序，即存在一组nums[i-1]

已知数组左边代表高数位，越往右边代表的数位越低，为了保证是下一个更大的数，如果nums中存在多组nums[i-1]

因此解题思路如下：

1.从右至左遍历数组nums，如果找到一个nums[pos1-1]

2.找到nums[pos1:]中的大于nums[pos1-1]的最小值，位置记录为pos2，注意如果pos1已经是nums的最后一个数，pos2直接等于pos1。

3.交换nums[pos1-1]与nums[pos2]的值。

4.对nums[i:]按照从小到大排序。

5.如果没有找到一对nums[pos1-1]

class Solution(object):
    def nextPermutation(self, nums):
        for pos1 in range(len(nums)-1,0,-1):
            if nums[pos1-1] nums[pos1 - 1] and nums[j] < nums[pos2]:
                            pos2 = j
                nums[pos1 - 1], nums[pos2] = nums[pos2], nums[pos1 - 1]
                nums[pos1:] = sorted(nums[pos1:])
                return nums
        nums = sorted(nums)
        return nums