題目:

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%)

我知道我寫得很爛,這題用寫的真的不好解釋
之後想到更好的寫法再編輯一下

那我們下題見