面试中算法（查找全排列的下一个数）

ゞ浴缸里的玫瑰 2024-05-28 10:22 80阅读 0赞

### 有一个正整数，找出这个正整数所有数字全排列的下一个数。 ###

> 就是在一个整数所包含数字的全部组合中，找到一个大于且仅大于原数的新整数。
> 
> 如果是固定的几个数字，应该是在逆序排列的情况下最大，在顺序排列的情况下最小。
> 
> 如果给出1、2、3、4、5这几个数字。
> 
> **最大的组合:54321。**
> 
>  **最小的组合:12345。**

### 具体步骤： ###

1.从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界。

2.让逆序区域的前一位和逆序区域中大于它的最小的数字交换位置。

3.把原来的逆序区域转为顺序状态。

![aca677046e3b42bc869d2d217c909552.png][]

![6302faa1e0d3409daed506905b7bd809.png][]

class MyAll:
        #查找逆序区域的边界
        def find(self,ll):
            #循环
            for i in range(len(ll)-1,0,-1):
                #判断后一个数大于前一个数，获取索引
                if ll[i]>ll[i-1]:
                    return  i
            return 0
    
    
        #逆序区域的前一位和逆序区域中大于它的最小的数字交换位置。
        def exchange(self,index,ll):
            #查找到逆序区域前一个数
            head=ll[index-1]
            #循环
            for i in range(len(ll)-1,0,-1):
                #判断前一个数<原来的数，则交换
                if head<ll[i]:
                    ll[index-1]=ll[i]
                    ll[i]=head
                    break
            return ll
    
    
        #把原来的逆序转为顺序
        def reverse(self,index,ll):
            i=index    #查找的位置
            j=len(ll)-1  #最后一个位置
            #循环
            while i<j:
                # 交换
                ll[i],ll[j]=ll[j],ll[i]
                i+=1
                j-=1
            return ll
    
        #显示数据
        def show(self,ll):
            for i in ll:
                print(i,end='')
            print()
    
        def find_all_num(self,ll):
            #1.从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界。
            index=self.find(ll)
            #如果数字边界是0，则已经是逆序了
            if index==0:
                return None
            #2.复制一个数列,防止被修改
            ll_copy=ll.copy()
            # 让逆序区域的前一位和逆序区域中大于它的最小的数字交换位置。
            self.exchange(index,ll_copy)
    
            #3.把原来的逆序转为顺序
            self.reverse(index,ll_copy)
            return ll_copy
    
    
    
    if __name__ == '__main__':
        my=MyAll()
        #初始化值12345
        list_num=list([1,2,3,4,5])
        #循环20个12345全排列整数
        for i in range(20):
            #调用方法，注意这个数列参数list_num，必须与左边的变量名字相同哦！！！
            list_num=my.find_all_num(list_num)
            #显示数据
            my.show(list_num)

![d2c53a2ce54c46c08ee31330235d4db6.png][] ![3f655957f0c446cf850ccc71a76e6376.png][]

> **每一步的时间复杂度都是O (n)，所以整体时间复杂度也是O (n) !**

[aca677046e3b42bc869d2d217c909552.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/35985f2a41984f0abb67e3960f1a076c.png
[6302faa1e0d3409daed506905b7bd809.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/9b65e56e3a884f4083774fcb338f6608.png
[d2c53a2ce54c46c08ee31330235d4db6.png]: https://img-blog.csdnimg.cn/direct/d2c53a2ce54c46c08ee31330235d4db6.png
[3f655957f0c446cf850ccc71a76e6376.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/95c4e6f0e0f94b41b9ae57703056e4b8.png