[LeetCode]179. 最大数(Largest Number)

题目描述

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

示例 1:

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

示例 2:

输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大,所以你需要返回一个字符串而不是整数。

解题思路

使用 Python3 的 sorted 函数直接比较,自定义比较函数。
注:Python3 的 sorted 和 sort 函数取消了 cmp 参数,所以需要通过 functools.cmp_to_key 来间接调用。
cmp 的自定义通过如下方式来实现:

1
2
3
4
5
6
7
def cmp(x, y):
if x < y: # 某种小于时,返回 -1
return -1
elif x > y: # 某种大于时,返回 1
return 1
else: # 等于时,返回 0
return 0

代码

Python 3.6

1
2
3
4
5
class Solution:
def largestNumber(self, nums: List[int]) -> str:
from functools import cmp_to_key
largest_num = "".join(sorted(map(str, nums), key=cmp_to_key(lambda x, y: int(y + x) - int(x + y))))
return "0" if largest_num[0] == "0" else largest_num

执行用时: 56 ms
内存消耗: 12.9 MB