最大数
题目要求
解题思路
今天的题目,让我们将一组数字重新组合,构成一个最大的整数。由于构成的整数非常大,所以返回结果需要字符串格式。
分析一下规律:
- 为了避免用int型或者long型越界,所以我们需要把数字先转换成字符串。然后可以把待比较的两个数字x,y组合成两个新的数字
string(x)+string(y)
和string(y)+string(x)
,比较一下哪种组合构成的数字更大。
首先**拼接成的两个字符串一定是等长的。**等长的字符串在比较的时候,是按照字符串的各个字符从前向后逐个比较的,所以相当于先比较了百分位,然后比较十分位,最后比较个位。所以在字符串等长的情况下,字符串大,那么对应的整形也更大。但两个不等长的字符串就没有这个结论了。
综上,我们按照下面的步骤:
1.先把nums
中的所有数字转字符串,形成字符串数组nums_str
;
2.比较两个字符串x,y
拼接结果x+y
和y+x
哪个更大,从而确定x
和y
谁排在前面,讲nums_str
降序排列;
3.把整个数组排序的结果拼接成一个字符串,并返回。
代码
class Solution:
def largestNumber(self, nums: List[int]) -> str:
from functools import cmp_to_key
key = cmp_to_key(lambda x,y: int(y+x)-int(x+y))
res = ''.join(sorted(map(str, nums), key=key)).lstrip('0')
return res or '0'
def bi(i):
if i == 0:
return 0
s = 0
k = i
while i >= 1 :
i=i/ 10
s+=1
return k /( 10 **s -1)
class Solution:
def largestNumber(self, nums: List[int]) -> str:
nums=sorted(nums,key=bi,reverse=True)
if nums[0] == 0:
return "0"
print(nums)
return "".join([str(i) for i in nums])
复杂度分析
时间复杂度:
O
(
N
∗
l
o
g
(
N
)
)
O(N* log(N))
O(N∗log(N))
空间复杂度:
O
(
N
)
O(N)
O(N)