Largest Number

题目

给定一个非负整数的列表，将它们排序之后首尾相连得到一个整数，返回可得的最大整数

Example 1:

Input: [10,2]
Output: “210”

Example 2:

Input: [3,30,34,5,9]
Output: “9534330”

解答

先将整数列表转化为字符串列表，再进行排序。

一般情况，对于两个整数字符串a和b，如果将a排在前面会使结果更大，则a的字典序一定比b大，可以直接使用>和<来进行比较。

特殊情况，a是b的前缀，则b的字典序一定比a大，但此时b不总是排在a的前面。对于'998'和'99899'，有'99899' > '998'。但是对于'338'和'33833'，我们必须确保'338' > '33833'，这与python3内置比较相反。因此我们需要自定义一个用于排序的比较函数。

不妨设a是b的前缀，由于两者前面相同，则需要对a和b的除去前缀的部分进行比较，也即比较a和b[len(a):]。如果b[len(a):] > a，则b > a；如果b[len(a):] < a，则b < a。此外，有一种特殊情况，最后a或b可能为空串，说明a和b都是由相同的子串（不同数量）拼接而成，这时返回相等。最终自定义的比较函数如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def cmp_str(a, b):
    if a == '' or b == '':
        return 0
        
    la = len(a)
    lb = len(b)
    if la <= lb and a == b[:la]:
        return cmp_str(a, b[la:])
        
    if la > lb and a[:lb] == b:
        return cmp_str(a[lb:], b)
        
    if a > b:
        return 1
    elif a == b:
        return 0
    else:
        return -1

对于排序，functools.cmp_to_key可以将比较函数转化为key参数，输入到sort()中。