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.
class Solution(object):
def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
if not nums: return None
i = len(nums)-1
j = -1
while i>0:
if nums[i-1]<nums[i]:
j= i-1
break
i -= 1
for i in range(len(nums)-1, -1, -1):
if nums[i]>nums[j]:
nums[i], nums[j]=nums[j], nums[i]
nums[j+1:]=sorted(nums[j+1:])
break
1 基本思路是，从后往前看，找上升的子序列，直到某一个数突然变小了，然后在这个数的后边找比它大的数中最小的那个，交换它们两个，交换后，再倒置一下后面的序列，即得到next permutation
2 从后往前找，找到第一个数字下降的地方，记录下这个位置，然后再回去从后往前找，找第一个比这个数大的数，swap它们两个，然后后面的再按升序排列
3 注意j要初始化为-1，代表特殊情况，原始序列全部是降序排列，它的next permutation是全部升序
4 在while循环里，如果nums[i-1]一直大于nums [i]，则j是不会有更新的，这就是全部降序，这种情况下j=-1
5 在交换元素后，sort后部分后，就需要跳出for循环
6 注意此处需要用sorted函数而不是str.sort()函数，sorted函数可以产生一个copy
