lc31:Next Permutation

Next Permutation Medium

2486

837

Add to List

Share Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

思路：替换法，因为要求不用额外空间，先定义一个逆序排列函数，然后从后往前找，[1,2,3], 找到第一个2<3,位置tag=1 从tag=1往后找找比nums[tag]大的第一个数，为3，替换2，3 [1,3,2] 然后把3往后的逆序排列

代码：python3

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(nums,i,j):
            while(i<j):
                nums[i],nums[j]=nums[j],nums[i]
                i=i+1
                j=j-1
            return nums
        tag=-1
        tagNum=0
        for x in range(len(nums)-1,-1,-1):
            if x-1>=0 and nums[x]>nums[x-1]:
                tag=x-1
                tagNum=nums[tag]
                break
        if(tag==-1):
            nums=reverse(nums,0,len(nums)-1)
        else:
            for y in range(len(nums)-1,tag,-1):
                if nums[y]>tagNum:
                    print(nums[y])

                    numY=nums[y]
                    nums[y]=tagNum
                    nums[tag]=numY
                    print(nums)
                    break
            nums=reverse(nums,tag+1,len(nums)-1)

tag:全排列公式：全排列数f(n)=n!(定义0!=1)，如1,2,3三个元素的全排列为： 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1 共321=6种。