[Leetcode][python]Next Permutation/下一个排列

╰半夏微凉° 2022-06-09 13:46 213阅读 0赞

## 题目大意 ##

寻找一组数排序的下一个序列  
例如：1，2，3，下一个就是1，3，2

## 解题思路 ##

官方思路（与下方相同）：[https://leetcode-cn.com/problems/next-permutation/solution/][https_leetcode-cn.com_problems_next-permutation_solution]

[http://fisherlei.blogspot.com/2012/12/leetcode-next-permutation.html][http_fisherlei.blogspot.com_2012_12_leetcode-next-permutation.html]

![这里写图片描述][Picture4.png]

图中文字翻译：

1.  从右向左，找到第一个违反生序的，也就是图中的6，叫他‘partitionnumber’。
2.  从右向左，找到第一个比刚才那个数大的数，叫他‘changenumber’。
3.  交换着两个数，然后把在partitionnumber右边的数顺序反过来。

## 代码 ##

class Solution(object):
        def nextPermutation(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            partition = -1
            for i in range(len(nums)-2, -1, -1):  # 从倒数第二个数开始遍历到第0个数 
                if nums[i] < nums[i+1]:  # 从后向前找到第一个升序对，并让partition等于升序对中较小的
                    partition = i
                    break
            if partition == -1:
                # 没找到升序对 e.g. 54321 --> 12345
                nums.reverse()
            else:
                for i in range(len(nums)-1, partition, -1):
                    # 交换partition和升序对后面比partition更大的数 如14532 -> 15432
                    if nums[i] > nums[partition]:
                        nums[i], nums[partition] = nums[partition], nums[i]
                        break
            # 将partition后面的数字逆向排序。由于找到的partition是从后向前的第一个升序对，所以可以放心partition后面一定都是降序的
            # 所以逆向排序后可以得到一个新的刚好大于之前permutation的next permutation
            # 比如此时14532已经变为15432，则再将5（此时partition已经是5了）后面的432逆序排列得到234.则最终的数字变为15234
            nums[partition+1:len(nums)] = nums[partition+1:len(nums)][::-1]  # 切片

## 总结 ##

[https_leetcode-cn.com_problems_next-permutation_solution]: https://leetcode-cn.com/problems/next-permutation/solution/
[http_fisherlei.blogspot.com_2012_12_leetcode-next-permutation.html]: http://fisherlei.blogspot.com/2012/12/leetcode-next-permutation.html
[Picture4.png]: http://4.bp.blogspot.com/-4zN0u5JG0vs/UN0xPEkP5yI/AAAAAAAAG9Q/O48ZfwB1i_c/s640/Picture4.png