leetcodeday31 –下一个排列

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

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

必须 原地 修改，只允许使用额外常数空间。

示例 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