这个题最直观的做法肯定是求出这个数组中所有数字的全排列，然后把每个排列拼起来，最后求拼起来的数字的最小值。但是我们知道n个数字共有n！个排列组合。这种算法显然是不够的，这道题其实是希望我们能找到一个排序规则，数组根据这个规则排序之后就能排成一个最小的数字。要确定排序规则，就要比较两个数字，也就是给出m和n，我们需要确定一个规则来判断m和n哪个应该排在前面，而不是仅仅比较这两个数字的大小。
根据题目要求，两个数字m和n能拼接成数字mn和nm，如果mn < nm，那么我们应该答应出mn，也就是m应该排在n的前面，我们定义此时m小于n；反之，如果nm < mn，则我们定义n小于m；如果mn = nm，则m等于n。接下去考虑怎么拼接数字，即给出数字m和n，怎么得到数字mn和nm病比较他们的大小。直接用数值不难办到，但是拼接数字可能会溢出，所以这也是一个隐形的大数问题。一个非常直观的方法就是将数字转换成字符串，另外，由于把数字m和n拼起来得到mn和nm，他们的位数想同，只需要按照字符串大小去比较大小即可。这个算法的时间复杂度是O（NlogN），空间复杂度是O（N）。
class Solution:
def minNumber(self, nums: List[int]) -> str:
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(strs) - 1)
return ''.join(strs)PREVIOUSlc400.第N个数字
NEXTjz046.把数字翻译成字符串