(Medium) 31. Next Permutation

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)