【Leetcode】31. Next Permutation 解题报告

给定一个数组，求下一个比当前数组组成的数大的数。
这道题也就是求从小到大下一个全排列，很简单，是个数学问题。
假设当前数组组成的数字为AB，其中

• B中的数都是递减的（或者前面的数大于等于后面的数）
• A最左边的a_right数小于B最右边的数
• 我们只需要将B中比a_right大的最小的那个数跟a_right互换位置再将B排列成最小的数（即递增）即可
  举个例子对于数字13541，我们按照如下方法
• 541是递减的，相当于上述的B
• 3小于5，我们将3与541中第一个比3大的数4与3互换，这样左边就是14，右边是531，再将531排个序变成135即可，最终得到14135

AC代码

class Solution:
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        flag_index = -1
        for i in range(len(nums)-1,0,-1):
            if nums[i] <= nums[i-1]:
                continue
            else:
                flag_index = i-1
                break
        if flag_index == -1:
            nums.sort()
        for i in range(len(nums)-1,flag_index,-1):
            if nums[i] > nums[flag_index]:
                nums[i], nums[flag_index] = nums[flag_index], nums[i]
                break
        nums[flag_index+1:] = sorted(nums[flag_index+1:])
        # return nums