leetcode 31 下一个排列 next permutation

目录

https://leetcode-cn.com/problems/next-permutation/

解题思路 交换 + 排序

交换：尝试把尽可能低位上的数字和它右边一个更大数字交换

排序: 然后把这个交换的数字右侧的数组排成升序

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i = len(nums) - 2
        minv = nums[n-1]
        while i >= 0 and nums[i] >= nums[i+1]:
            i -= 1
        j = n - 1
        while j > i:
            if nums[j] > nums[i]:
                nums[i], nums[j] = nums[j], nums[i]
                while True: # 冒泡排序
                    f = True
                    k = i + 1
                    while k < n - 1:
                        if nums[k] > nums[k+1]:
                            nums[k], nums[k+1] = nums[k+1], nums[k]
                            f = False
                        k += 1
                    if f: 
                        return
            j -= 1
        nums.sort()