题解 | #没有重复项数字的全排列#
没有重复项数字的全排列
https://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1
语言：python
思路： 用数学归纳法
先给数组升序，然后该数组添加为总数组第0项。根据归纳法，我们想要在有第j-1项时推出第j项。
例如，13542后的一项，是14235，后一项其实就是比前一项大的排列中最小的排列。
从后往前遍历，如果后一个数字比前一个小，例如13542的尾数2比他前面的4小，那调整他俩的顺序变为1324没办法让这个数变大。所以继续往前找，找到13542的第三项5比第二项3大，调整第二项可以最小化的让该数变大。所以从3后面的2，5，4中取出比3大却又是比3大的之中最小的4来替换3，剩下的2，3，5按升序排列，就得到了最小的比13542大的序列14235.
用该算法遍历，解决问题。
import math class Solution: def permute(self, num: List[int]) -> List[List[int]]: # write code herek=len(num) num.sort() #给原数组升序 k=len(num) #长度 cb=[]#总输出的数组命名为combination的缩写cb cb.append(num) #第零个是原数组升序 j=1 #j是数组的序号，比方说【1，2，3】为总数组cb的第零项。 while j<math.factorial(k): # #一共有长度的阶乘个数组排列 i=1 while cb[j-1][k-i]<=cb[j-1][k-i-1]: i+=1 #从后往前找出要调整的节点的位置，13542中的3，他比后一个小 m=1 while cb[j-1][k-m]<=cb[j-1][k-i-1]: m+=1 #找出节点应该换上的元素，13542中3后面的5，4，2里比3大又最小的元素 rest = cb[j - 1][ k- i-1 : k - m] + cb[j - 1][ k- m + 1 : ] rest.sort() # 除去前面不变的的元素和更换的新值，剩下的进行升序扔最后 hd=cb[j - 1][: k- i - 1] #节点前面的部分，如13542中的1无需变更 cg=[cb[j - 1][k-m]] #需要放进节点的元素，13542中的4 nxt=hd+cg+rest #拼接出13542后面的一个元素，1，4，2，3，5 cb.append(nxt)# 贴进总表 j+=1 #遍历下一个数 return cb
投递美团等公司9个岗位