2.7　最大数

题目描述（第179题）

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例1

输入：[10,2]

输出：210

示例2

输入：[3,30,34,5,9]

输出：9534330

说明：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

思路

这道题其实是排序题目的变种，是一道披着数学外衣的排序题。

首先我们要知道一个数学常识。

1．如果两个数位数不同，那么位数大的数更大。

2．如果两个数位数相同，比如两个数123a456和123b456，如果a> b，那么123a456大于123b456，否则123a456小于或等于123b456。也就是说，两个相同位数的数的大小关系取决于第一个不同的数字的大小。

这道题由于总的位数是确定的，就是数组全部位数之和，因此我们的入手点就是上面提到的第2点，即越高位的数字越大越好，但是这里需要考虑特殊情况，题目给出的测试用例就能够很好地说明问题。示例2中按降序排序得到的数是9534303，然而交换3和30的位置可以得到正确答案9534330，因此，在排序的比较过程中，我们需要自定义排序的策略，即自己决定哪个元素排在前面。一种方式是将比较元素（即题目中的非负整数）转化为字符串，然后用字符串的比较即可避免上述问题。比如上述例子中的3和30，按照拼接后的字符串比较'303'和'330'哪个大，从而决定谁排在前面就好了。

我们可以先将数字数组转化为字符串数组，然后排序，这个过程需要定制比较逻辑。和其他编程语言一样，Python支持这种自定义的比较逻辑，如果你不熟悉也没关系，这里简单地讲解一下，熟悉的读者可以选择跳过本部分内容。

对于s.sort(reverse=True,key=functools.cmp_to_key(comp))而言，comp是我们自定义的比较函数，它接收两个参数，分别是a和b，表示需要进行比较的两个元素。接下来是重点。

●　如果返回值为正，则b在前，a在后。

●　如果返回值为负，则a在前，b在后。

●　如果返回值为0，则保持相对位置不变。

你只需要自定义并实现比较逻辑，然后返回正数、负数或0即可。

代码

如果你喜欢短小精悍的代码，可以参考下面这段代码。

复杂度分析

●　时间复杂度：这里总的时间复杂度是由排序决定的，因此这种算法的时间复杂度为O(nlogn)，其中n为数组长度。

●　空间复杂度：由于我们将输入转化成了字符串数组，因此这里的空间复杂度为O(n)，其中n为数组长度。

扩展

如果改为求最小数该怎么做？我们的解题策略需要做怎样的调整？