搜遍全网也没有一个满意的python题解，自己上手写一个
正巧前段时间刚总结了回溯，看到这道题第一反应，用回溯做全排列，然后快排，找最小数，有点暴力==，答案先贴一个，别急着抄答案，下面有更优解法。
class maxNum():
def permutation(self, arr):
tmp, res = [], []
used = [False for _ in range(len(arr))]
def dfs(depth):
if depth == len(arr):
res.append(tmp[:])
return
for idx in range(len(arr)):
if used[idx] == False:
tmp.append(arr[idx])
used[idx] = True
dfs(depth+1)
tmp.pop()
used[idx] = False
if len(arr) == 0: return []
dfs(0)
return res
def getMax(self, arr):
per = self.permutation(arr)
if per == []: return []
nums_list = []
for i in per:
num_str = ''
for j in i:
num_str += str(j)
nums_list.append(int(num_str))
nums_list = sorted(nums_list) # 此处省略快排
return nums_list[0]
回溯全排最坏情况下时间复杂度：O(N×N!)，并不理想，简单问题被复杂化了
只需遍历一次数组，index从1至len(arr), 每次都与arr[0]比较，若int(str(arr[0]) +str(arr[index])) > int(str(arr[index]) +str(arr[0])), 则将arr[index]移至数组首位
def printMinNum(nums):
for i in range(len(nums)):
if int(str(nums[0]) + str(nums[i])) > int(str(nums[i]) + str(nums[0])):
nums.insert(0, nums.pop(i)) #列表第i个值移动到首位
nums = [str(k) for k in nums]
return int(''.join(nums))
