本文主要是介绍面试中算法(查找全排列的下一个数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
有一个正整数,找出这个正整数所有数字全排列的下一个数。
就是在一个整数所包含数字的全部组合中,找到一个大于且仅大于原数的新整数。
如果是固定的几个数字,应该是在逆序排列的情况下最大,在顺序排列的情况下最小。
如果给出1、2、3、4、5这几个数字。
最大的组合:54321。
最小的组合:12345。
具体步骤:
1.从后向前查看逆序区域,找到逆序区域的前一位,也就是数字置换的边界。
2.让逆序区域的前一位和逆序区域中大于它的最小的数字交换位置。
3.把原来的逆序区域转为顺序状态。
class MyAll:#查找逆序区域的边界def find(self,ll):#循环for i in range(len(ll)-1,0,-1):#判断后一个数大于前一个数,获取索引if ll[i]>ll[i-1]:return ireturn 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]=headbreakreturn ll#把原来的逆序转为顺序def reverse(self,index,ll):i=index #查找的位置j=len(ll)-1 #最后一个位置#循环while i<j:# 交换ll[i],ll[j]=ll[j],ll[i]i+=1j-=1return 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_copyif __name__ == '__main__':my=MyAll()#初始化值12345list_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)
每一步的时间复杂度都是O (n),所以整体时间复杂度也是O (n) !
这篇关于面试中算法(查找全排列的下一个数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!