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

Solutions

刚开始可以使用暴力求解试下:

# -*- coding:utf-8 -*-
import itertools
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if numbers is None:
            return None
        str_numbers = [str(i) for i in numbers]
        perms = itertools.permutations(str_numbers)
        res = [''.join(item) for item in perms]
        return min(res)

上面因为涉及到全排列,$O(n!)$ 的复杂度肯定是难以接受的。于是参考书本上的做法,如果 ab < ba,那么就选些 ab 的组合,按照这个规则,我们对数列中所有的两个数进行排序,两两组合值最小的排在最前面。为了实现这个想法,可以在现有的排序基础上,将比较算法改变成这里的比较规则:cmp(a+b, b+a),这里当然首先要将数字编程字符串再进行连接(+)操作。

# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if numbers is None:
            return None
        str_numbers = [str(i) for i in numbers]
        res = sorted(str_numbers, cmp=lambda x, y: cmp(x+y, y+x))
        return ''.join(res)

References

  1. 033. 把数组排成最小的数