Skip to content

031 next permutation

31. Next Permutation

题目: https://leetcode.com/problems/next-permutation/

难度:

Medium

参照wikipedia:

https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

首先,关于什么是全排列不做解释。如果一个排列为A,下一个排列为A_NEXT,那么A_NEXT一定与A有尽可能长的公共前缀。

看具体例子,一个排列为124653,如何找到它的下一个排列,因为下一个排列一定与124653有尽可能长的前缀,所以,脑洞大开一下,从后面往前看这个序列,如果后面的若干个数字有下一个排列,问题就得到了解决。

第一步:找最后面1个数字的下一个全排列。

124653,显然最后1个数字3不具有下一个全排列。

第二步:找最后面2个数字的下一个全排列。

124653,显然最后2个数字53不具有下一个全排列。

第三步:找最后面3个数字的下一个全排列。

124653,显然最后3个数字653不具有下一个全排列。

------插曲:到这里相信大家已经看出来,如果一个序列是递减的,那么它不具有下一个排列。

第四步:找最后面4个数字的下一个全排列。

124653,我们发现显然最后4个数字4653具有下一个全排列。因为它不是递减的,例如6453,5643这些排列都在4653的后面。

我们总结上面的操作,并总结出重复上面操作的两种终止情况:

1:从后向前比较相邻的两个元素,直到前一个元素小于后一个元素,停止

2:如果已经没有了前一个元素,则说明这个排列是递减的,所以这个排列是没有下一个排列的。

124653这个排列终止情况是上面介绍的第一种,从后向前比较相邻的2个元素,遇到4<6的情况停止。

并且我们可以知道:

1:124653和它的下一个排列的公共前缀为12(因为4653存在下一个排列,所以前面的数字12保持不变)

2:4后面的元素是递减的(上面介绍的终止条件是前一个元素小于后一个元素,这里是4<6)

现在,我们开始考虑如何找到4653的下个排列,首先明确4后面的几个数字中至少有一个大于4.

4肯定要和653这3个数字中大于4的数字中(6,5)的某一个进行交换。这里就是4要和6,5中的某一个交换,很明显要和5交换,如果找到这样的元素呢,因为我们知道4后面的元素是递减的,所以在653中从后面往前查找,找到第一个大于4的数字,这就是需要和4进行交换的数字。这里我们找到了5,交换之后得到的临时序列为5643.,交换后得到的643也是一个递减序列。

所以得到的4653的下一个临时序列为5643,但是既然前面数字变大了(4653--->5643),后面的自然要变为升序才行,变换5643得到5346.

所以124653的下一个序列为125346.

看一个permutation,比如

125430

  • 从末尾开始,找到decreasing subsequence,5430,因为来调5330无论怎么调,都不可能有比它更小的,数也被自然的分成两部分(1,2) 和 (5,4,3,0)
  • 下一步是找这个sequence里面第一个比前面部分,比2大的,3,也很容易理解,因为下一个必定是(1,3)打头
  • 交换 3和2 ,变成 (1,3,5,4,2,0),再把后面的部分reverse,得到后面部分可得到的最小的

这个时候,得到下一个sequence 130245

AC 代码

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if len(nums) <= 1:
            return
        idx = 0
        for i in range(len(nums)-1, 0, -1):
            if nums[i] > nums[i-1]: # find first number which is smaller than it's after number
                idx = i
                break
        if idx != 0: # if the number exist,which means that the nums not like{5,4,3,2,1}
            for i in range(len(nums)-1, idx-1, -1):
                if nums[i] > nums[idx-1]:
                    nums[i], nums[idx-1] = nums[idx-1], nums[i]
                    break

        nums[idx:] = nums[idx:][::-1]


回到顶部