s输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例1：

输入：[10,2]
输出："102"

示例2：

输入：[3,30,34,5,9]
输出："3033459"

提示：

• 0 < nums.length <= 100

说明：

• 输出结果可能非常大，所以你需要返回一个字符串而不是整数
• 拼接起来的数字可能会有前导0，最后结果不需要去掉前导0

class Solution:
	def minNumber(self, nums):

解题思路：

• 此题求拼接起来的”最小数字”，本质上是一个排序问题。

算法流程：

1. 初始化：字符串列表strs，保存各数字的字符串格式；
2. 列表排序：应用以上”排序判断规则”，对strs执行排序。
3. 返回值：拼接strs中的所有字符串，并返回。

复杂度分析：

• 时间复杂度$O(NlogN)$：$N$为最终返回值的字符数量($strs$列表的长度<=N)；使用快排或内置函数的平均时间复杂度为$O(NlogN)$，最差为$O(N^2)$。
• 空间复杂度$O(N)$：字符串列表$strs$占用线性大小的额外空间。

代码：

本节只列举快速排序和内置函数两种排序方法，其他排序方法也可使用。

快速排序：

需修改快速排序函数中的排序判断规则。字符串大小(字典序)对比的实现方法：

• Python/C++中直接用<，>；
• Java中使用A.compareTo(B)。

class Solution:
	def minNumber(self, nums):
		def fast_sort(l, r):
			if l >= r: return
			i, j = l, r
			while i < j:
				while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: j-= 1
				while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: i += 1
				strs[i], strs[j] = strs[j], strs[i]
			strs[i], strs[l] = strs[l], strs[i]
			fast_sort(l, i-1)
			fast_sort(i+1, r)
		strs = [str[num] for num in nums]
		fast_sort(0, len(str) - 1)
		return ''.join(strs)

内置函数：

需定义排序规则：

• python定义在函数sort_rule(x,y)中；

class Solution:
	def minNumber(self, nums):
		def sort_rule(x, y):
			a, b = x+y, y+x
			if a > b: return 1
			elif a < b: return -1
			else: return 0
		strs = [str(num) for num in nums]
		strs.sort(key = functools.cmp_to_key(sort_rule))
		return ''.join(strs)