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

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注