题目描述:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{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)