leetcode 31. 下一个排列(python)

﹏ヽ暗。殇╰゛Y 2022-05-13 19:56 175阅读 0赞

**【前言】**

python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/details/89470836][https_blog.csdn.net_weixin_40449300_article_details_89470836]

github链接：[https://github.com/Teingi/test][https_github.com_Teingi_test]

**【正文】**

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须**[原地][Link 1]**修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。  
`1,2,3` → `1,3,2`  
`3,2,1` → `1,2,3`  
`1,1,5` → `1,5,1`

--------------------

### **升序倒置法** ###

class Solution:
        def nextPermutation(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            i = len(nums) - 1
            if len(list(set(nums))) != 1:
                
                #先从尾部升序结束的点
                while i - 1 >= 0:
                    if nums[i] <= nums[i - 1]:
                        i = i - 1
                    else:
                        break
                #如果前面还有至少一个位置
                if i - 1 >= 0:
                    j = i - 1
     
                    t = len(nums) - 1
                    #从后往前找第一个大于j位置上的数
                    while nums[t] <= nums[j]:
                        t -= 1
                    nums[t], nums[j] = nums[j], nums[t]
                    a = sorted(nums[i:])
                    a_index = 0
                    #因为我不知道python分段排序的方法，于是就手动排序
                    #以下是对nums的排序
                    for index in range(i, len(nums)):
                        nums[index] = a[a_index]
                        a_index += 1
                #没有位置则sort
                else:
                    nums.sort()

[https_blog.csdn.net_weixin_40449300_article_details_89470836]: https://blog.csdn.net/weixin_40449300/article/details/89470836
[https_github.com_Teingi_test]: https://github.com/Teingi/test
[Link 1]: https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95