實(shí)現(xiàn)獲取下一個(gè)排列的函數(shù)，算法需要將給定數(shù)字序列重新排列成字典序中下一個(gè)更大的排列。
如果不存在下一個(gè)更大的排列，則將數(shù)字重新排列成最小的排列（即升序排列）匾七。
必須原地修改，只允許使用額外常數(shù)空間江兢。
以下是一些例子昨忆，輸入位于左側(cè)列，其相應(yīng)輸出位于右側(cè)列杉允。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
思路：
124653 --> 125346
125430 --> 130245
從右向左找邑贴，只有找到前一位nums[i-1]小于當(dāng)前位nums[i]的，排列后才可能比當(dāng)前數(shù)字大夺颤；將nums[i-1]和右邊找到的剛好大于nums[i-1]的數(shù)字作交換痢缎，最后把交換后的nums[i:]從小到大排列胁勺，保證結(jié)果最小世澜，即nums[i:]倒序，因?yàn)榻粨Q后nums[i:]仍是從大到小署穗。
class Solution:
def nextPermutation(self, nums):
n = len(nums)
for i in range(n - 1, 0, -1):
if nums[i-1] < nums[i]:
for j in range(n-1, i-1, -1):
if nums[j] > nums[i-1]:
nums[j], nums[i-1] = nums[i-1], nums[j]
nums[i:] = nums[i:][::-1]
return
else:
nums.reverse()
su = Solution()
nums = [3,2,1]
su.nextPermutation(nums)
print(nums)
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]
