Jianbo Dai's

lc031.下一个排列

 
  • Dec 04, 2020

题目链接

做过一个类似的生成各种不同的排列的题目，如果不是原地返回的话，可以先生成所有排列然后进行排序然后取下一个，我翻出了之前的记录写了一下给定字符生成各个排序的集合。但是这题要求原地返回并且将所有排列全都求出来也非常地浪费时间，因此必须要有一种方法能够直接求出下个排列。对于下个排列，我们有两个发现：一就是我们需要将一个左边的”较小数“与右边的一个”较大数“交换，以能够使当前排列变大，从而得到下一个排列；二就是，我们同时要让这个”较小数“尽量靠右而”较大数“尽可能小。当交换完成后，”较大数“右边的数需要按照升序重新排列，这样才能保证新排列大于原来排列的情况下，变大的幅度尽可能小。

那么如何具体实现上述的思想呢。首先，我们先找“较小数”，我们从后往前寻找第一个顺序对(i, i+1)，满足nums[i] < nums[i+1]，这个nums[i]就是“较小数”，并且[i+1, n)必为下降序列。如果找到了顺序对后，我们在区间[i+1, n)中从后向前找第一个大于“较小数”的数，也就是“较大数”。接下去我们交换“较小数”与“较大数”的位置，并且将[i+1, n)区间重新排成升序，我们能证明此时该区间内的数字是严格递减的，因此我们可以直接反转区间从而得到答案。注意到如果原先的数列已经是最大的排列时，在第一个找顺序对的步骤中我们就无法找到，我们在此时可以跳过步骤二直接将整个区间逆序。

该算法的实现如下，时间复杂度是O（N），空间复杂度是O（1）。啊我在知道思路的情况下一直都没有完全写对，原来是因为一是偷懒用了[::-1]来翻转字符串导致没有在原地修改，二是我没有在找到“较小数”与”较大数“之后及时break，导致后续处理一直在进行从而错误。

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        def reverse(nums, start, end):
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1

        flag = False
        for i in range(len(nums)-2, -1, -1):
            if nums[i+1] > nums[i]:
                flag = True
                print("i:", i)
                break
        if not flag:
            reverse(nums, 0, len(nums)-1)
        else:
            for j in range(len(nums)-1, i, -1):
                if nums[j] > nums[i]:
                    nums[j], nums[i] = nums[i], nums[j]
                    reverse(nums, i+1, len(nums)-1)
                    break
Search