每日一题20201118（31. 下一个排列）

31. 下一个排列

image-20201118141644763

思路

首先说一下什么是字典序，把1 2 3当作a b c的话，abc有6种排列顺序。

abc acb bac bca cab cba

上图就是字典序，题目的要求狠简单： 找到下一个字典序，如果没有的话，则输出最小的序号。

首先明确一下，没有下一个序列的情况，那么就是大的全部在前面，所以只需要反转数组就行，就可以回到最小的序列。

再看有下一个排序的情况，我们需要先从右侧找到一个比最右边数字小的数.

然后再和右边第一个大于这个数的数进行交换，以571632为例子：

第一个小于右侧数字的数是1，第一个大于1的数字是2，交换之后:

572631, 由于之前确定的，是通过升序找到的1，所以还需要反转2后面的数字: 572136 就是最终结果了！

正好可以和上面反转的一起处理。

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 左侧的第一个非升序数字，这里也可以len(nums)-2
        j = len(nums)-1
        while j-1 >= 0:
            if nums[j] > nums[j-1]:
                break
            j -= 1
        # 如果j-1>=0说明找到了这个数字，否则说明数组
        # 是降序排列的
        if j-1 >= 0:
            right = len(nums)-1
            # 找到右边第一个大于nums[j-1]的数字
            while right > j-1 and nums[right] <= nums[j-1]:
                right -= 1
            # 交换他们
            nums[j-1], nums[right] = nums[right], nums[j-1]
            self.reverse(nums, j, len(nums)-1)
        else:
            self.reverse(nums, 0, len(nums)-1)
            
    # 反转数组
    def reverse(self, nums, i, j):
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1
        return nums

image-20201118142757008