#31 Next Permutation———Top 100 Liked Questions

超、凢脫俗 2022-04-25 06:30 97阅读 0赞

Implement **next permutation**, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be **[in-place][]** and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

`1,2,3` → `1,3,2`  
`3,2,1` → `1,2,3`  
`1,1,5` → `1,5,1`

> """
> 
> 第一次：字典序算法。在提交过程中，1）当nums是降序排列时，直接将倒序的nums返回，第一次写的return语句，出错，第二次直接nums = sorted(nums)，结果也是错的，后又改成nums.sort()，就可以了。题目要求就地改变in-place！因此不能写return语句，这样需要设置flag位，以保只需要找第一个左边小于右边值的i。
> 
> 区别：sorted(iterable,key=None,reverse=False，返回新的列表，对所有可迭代的对象均有效
> 
>             sort(key=None,reverse=False) 就地改变列表  reverse：True反序；False 正序
> 
>  
> 
> """
> 
>     class Solution(object):
>         def nextPermutation(self, nums):
>             """
>             :type nums: List[int]
>             :rtype: None Do not return anything, modify nums in-place instead.
>             """
>             flag = 0
>             for i in range(len(nums) - 2, -1, -1):
>                 if nums[i] < nums[i + 1]:
>                     for j in range(len(nums) - 1, -1, -1):
>                         if nums[j] > nums[i]:
>                             nums[i], nums[j] = nums[j], nums[i]
>                             nums[i + 1:] = sorted(nums[i + 1:])
>                             flag = 1
>                             break
>                 if flag:
>                     break
>             if not flag:
>                 nums.sort()                                #1)
> 
> """
> 
> Runtime: 24 ms, faster than 99.74% of Python online submissions for Next Permutation.
> 
> Memory Usage: 11.9 MB, less than 5.74% of Python online submissions for Next Permutation.
> 
> """

>  字典序算法：
> 
> ①字典序示例：123， 132， 213， 231， 312， 321
> 
> ②字典序算法：如果当前排列时124653，找它的下一个排列的方法如下：从右到左遍历，找到第一个左邻小于右邻的数，如果找不到， 说明排列求解完成，否则没完成。在124653中找到46，记录4的位置i，然后再从右到左遍历，找到第一个大于4的数，这是是5，记录5的位置为j，将4和5交换，此时排列为125643，最后对于i位置之后的数即643进行升序排列，即346，得到的125346是124653的下一个字典序。
> 
> 参考：[字典序算法][Link 1]

[in-place]: http://en.wikipedia.org/wiki/In-place_algorithm
[Link 1]: https://www.cnblogs.com/darklights/p/5285598.html