Leetcode179.最大数

题目描述：

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

示例1：

输入: [10,2]
输出: 210

示例2：

输入: [3,30,34,5,9]
输出: 9534330

说明：

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

自身解题想法：

通过对整数进行散列，建立一个嵌套列表，索引为1的列表里面的元素为以1起始的整数，例如：1、123、1001等。对嵌套列表中的每个列表进行排序，最后以逆序的方式将int型元素转化为str型元素进行相加。

image.png

问题之处：

由于结果int('3' + '30' ) = 330 > int('30' + '3') = 303，所以以整数的排序进行的相加不符合条件要求，例如：[3, 30, 34, 3005]为按整数排序的结果，字符化相加操作后为'343005303'('34|3005|30|3')，而实际上的最大值应该是'343303005'('34|3|30|3005')。造成这种差异在于如果一个整数起始数字后面一位或几位为0，那么这个数要区别对待，例如：int('34' + '305' ) = 34305 > int('305' + '34') = 30534、而int('30' + '34' ) = 3034 < int('34' + '30') = 3430。所以排序应该以这种形式[3005, 303, 3, 34]，然后反序相加。

如何实现：

我们知道，如果对字符串进行排序，它会按照字典的形式进行排序，例如：

>>> a = ['1', '101', '201', '1005']
>>> a.sort()
>>> a
['1', '1005', '101', '201']

"""同理"""
>>> a=['3005', '303', '3', '34']
>>> a.sort()
>>> a
Out[87]: ['3', '3005', '303', '34']

与我们的想法存在差异，我们需要得到的是['3005', '303', '3', '34']

标准解答：

image.png

解析：

这里对内置类str的（小于）方法lt进行继承覆盖
原方法文档如下：

image.png
这两者有何区别呢?
我们运行下代码：
image.png
image.png
由结果分析可知，排序以字符串相比较的方式，原来的内置函数str.lt(x, y) 若返回True，则x小于y，排序以x在前y在后，结果为递增的形式排列。
经过修改后的类继承了str类的特性，但是覆盖了lt方法的实现，若x + y>y + x，则x在前，y在后，结果以递减的形式排列。
若想得到我们先前的结果，只需要修改为 x + y < y + x 即可。