实现获取 下一个排列 的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列(即,组合出下一个更大的整数)。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须 原地 修改,只允许使用额外常数空间。
示例 1:
输入:nums = [1,2,3] 输出:[1,3,2]
示例 2:
输入:nums = [3,2,1] 输出:[1,2,3]
示例 3:
输入:nums = [1,1,5] 输出:[1,5,1]
示例 4:
输入:nums = [1] 输出:[1]
第一次做法:思路,找到 需要交换的nums[i] 和nums[j],交换后,对nums[i+1:]进行排序即可
# @lc code=start
class Solution:
def InsertSort(self,lst):
n=len(lst)
if n<=1:
return lst
for i in range(1,n):
j=i
target=lst[i] #每次循环的一个待插入的数
while j>0 and target<lst[j-1]: #比较、后移,给target腾位置
lst[j]=lst[j-1]
j=j-1
lst[j]=target #把target插到空位
return lst
def nextPermutation(self,nums) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
m=j=len(nums)-1
x=-1
for i in range(len(nums)-2,-1,-1):
re=100
l=j
for h in range(j,m+1):
if 0<nums[h]-nums[i]<re:
l=h
re=nums[h]-nums[i]
print(l)
if nums[i]<nums[l]:
rev=nums[l]
nums[l]=nums[i]
nums[i+1:]=self.InsertSort(nums[i+1:])
nums[i]=rev
return nums
else:
j=j-1
n=0
while n<m:
rev=nums[m]
nums[m]=nums[n]
nums[n]=rev
n+=1
m-=1
return nums