题目描述: 设有n个正整数,将他们连接成一排,组成一个最大的多位整数. 例如:3个整数13,312,343,连成的最大整数为:34331213 又如:4个整数7,13,4,246连接成的最大整数为7424613 现在给你一个正整数列表L,请你输出用这些正整数能够拼接成的最大整数。
note:测试数据已于2014年11月13日更新,以前通过的代码不一定能够再次通过。
示例:
输入: L = [13, 312, 343] 输出: 34331213
分析: 初步分析和字典序有关系。 如果现在有两个数 4, 123, 那么最大的就是4123。 但是对于 32432 和 324 最大的应该是 32432432,而不是简单按照字典序排序得到的 32432324 所以,我们要重写一下字典序的排序,当出现上面的这种情况的时候,再多进行一些判断。
上面的是什么情况呢? 就是 当一个字符串结束了以后,另外一个字符串还有剩下的时候,就需要再进行额外的排序。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
L = [str(a) for a in L]
from functools import cmp_to_key
# 在 python 的时候, 需要 return 1 和 -1, 这个和 c 和 c++ 还是有点点区别的。
def cmp(x, y):
# print(x, y)
len_x, len_y = len(x), len(y)
i = 0
tx = [_ for _ in x]
ty = [_ for _ in y]
while True:
if tx[i] > ty[i]:
return 1
elif tx[i] < ty[i]:
return -1
else:
i += 1
# 到这里的时候,就表述比较完了一个字符串,需要进行下一轮的比较了。
if i == len_x and i == len_y:
return 0
if i == len_x:
tx += x
len_x = len(tx)
if i == len_y:
ty += y
len_y = len(ty)
L.sort(key=cmp_to_key(cmp), reverse=True)
print("".join(L))精彩马上继续。。。。。