欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode——31. 下一个排列

程序员文章站 2022-04-28 20:41:16
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]输出:[...

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