剑指offer：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个 python版本

搜遍全网也没有一个满意的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))