乘风原创程序

  • LeetCode——31. 下一个排列
  • 2021/2/23 11:18:00
  • 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