leetcode with python:31. Next Permutation

题目:

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

For example, for arr = [1,2,3], the following are considered permutations of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.

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

给定我们一阵列,找出它的下一个排列顺序,且不能用额外空间
排列顺序範例:[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

说实话这题在看到时我完全看不出那些排列顺序的规律
自然也是完全没有头绪,直到看了讨论区的解说才稍稍了解

class Solution:    def nextPermutation(self, nums: List[int]) -> None:        """        Do not return anything, modify nums in-place instead.        """        l=len(nums)                        if l<=2:            nums.reverse()            return                x=l-2        while x>=0 and nums[x]>=nums[x+1]:            x=x-1                    if x==-1: #若已是最后一项,反转变回第一项            nums.reverse()            return                for i in range(l-1,x,-1):            if nums[i]>nums[x]:                nums[i],nums[x]=nums[x],nums[i]                break                nums[x+1:]=reversed(nums[x+1:])        return

先解说它的规律好了,每个位置优先选最小的数
所以第一个阵列会是由小到大,最后一个是由大到小
依照此原则由后开始进行数字的替换
ex:
[1,2,3]第三位无其他可能:第二位只能改选3,第三位只能改选2=>

[1,3,2]第二,三位无其他可能:第一位改选2(优先选最小的数),第二位改选1(优先选最小的数),第三位只能改选3=>

[2,1,3]第三位无其他可能:第二位只能改选3,第三位只能改选1=>

[2,3,1]第二,三位无其他可能:第一位只能改选3,第二位改选1(优先选最小的数),第三位只能改选2=>

[3,1,2]第三位无其他可能:第二位只能改选2,第三位只能改选1=>

[3,2,1]

所以要找出下一个排序
由后往前看,若遇到数字由大变小时,标记该位index(x)
尾端往前找第一个比nums[x]大的数字,将两者交换,再把x之后的元素reverse即可

其实就是找出离尾端最近可以改选的数(若一部分都为降序表示该部分已达最后一个可能)
第一次出现升序的数即为第一个还有其他可能能选的数
接着将要改写的数优先选最小的数(尾端往前找第一个比nums[x]大的数字,两者交换)
然后后面的部分变为升序排列(因为后面的也都优先选最小的数)
而它们原本就是降序了,所以只要reverse就全体变为升序了
最后执行时间45ms(faster than 91.99%)

我知道我写得很烂,这题用写的真的不好解释
之后想到更好的写法再编辑一下

那我们下题见