把数组排成最小数

题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

解答

第一步，递归，找出所有的组合结果；

第二部，找出最小组合的值。

# coding:utf-8
class Solution:
    def Permutation(self, numbers):
        if len(numbers) == 0:
            return ''
        if len(numbers) == 1:
            return numbers[0]
        # 所有组合结果
        ret = self.pj(numbers)
        n2 = []
        # 找出最小数
        for i in ret:
            nu = ''
            for j in i:
                nu += str(j)
            nu = int(nu)
            if n2 == []:
                n2.append(nu)
            else:
                if nu >= n2[-1]:
                    n2.append(n2[-1])
                else:
                    n2.append(nu)

        return n2[-1] if n2[-1] else None

    def pj(self,ss):
        if len(ss) == 0:
            return []
        if len(ss) == 1:
            return ss
        l1 = []
        for i in range(len(ss)):
            probe = [ss[i]]
            for j in self.pj(ss[:i]+ss[i+1:]):
                if type(j) == int:
                    head = probe
                    head.append(j)
                else:
                    head = probe + j
                l1.append(head)
        return l1

p = Solution()
ret = p.Permutation([1,2])
print ret

结束！