LeetCode——31. 下一个排列

31. 下一个排列

题目

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

 

示例 1：

输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：

输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]
示例 4：

输入：nums = [1]
输出：[1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解思路

1>源代码

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        i = length-2
        while i>=0 and nums[i]>=nums[i+1]:
            i-=1
        if i>=0:
            j = length-1
            while j>=0 and nums[j]<=nums[i]:
                j-=1
            nums[j], nums[i] = nums[i], nums[j]
        left = i+1
        right = length-1
        while left<right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
        

2>算法介绍

本题其实是一道找规律的题，我们以[4, 6, 5, 2, 3, 1]的下一次排列为例，很明显他的下一次排列是[4, 6, 3, 1, 2]，主要思路是：

首先从右往左遍历，找到第一个不满足单调增的值，本例中为2；

然后再次从右往左遍历，找到第一个大于2的值，本例为3；

交换以上两个元素，并将3此时所在的位置右边进行递增排序。

根据以上思路就可以完成代码，不过需要注意的是，nums已经为倒序的情况。

本文地址：https://blog.csdn.net/HizT_1999/article/details/113965442