算法第二十二天-最大数

最大数

题目要求

解题思路

今天的题目，让我们将一组数字重新组合，构成一个最大的整数。由于构成的整数非常大，所以返回结果需要字符串格式。
分析一下规律：

• 为了避免用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\ast log(N))$
空间复杂度：$O(N)$