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

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

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

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Example 4:

Input: nums = [1]
Output: [1]

Constraints:

 1 <= nums.length <= 100
 0 <= nums[i] <= 100

題意

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

排列組合 且 下一個組合 的數字比 上一個大 : EX 1 EX 3
除了 到底的排列 : EX 2 ，則 全部翻轉(reverse)過來

解法

• 三步驟:
  Step 1: 右往左 找第一個降下來的數字 : 右數字比左數字大
  Step 2: Step 1 找到的數字 與 其右邊部分數字堆中 由右到左 找比找到的數字大的第一個數字 進行對調
  Step 3: 在把右半邊 翻轉

Tip Source: LeetCode 31 / Solution / Approach 2: Single Pass Approach
圖像解法動畫
Code

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

Result 電腦解Code，躺床時繼續想個，想通則手機AC(Success)