题解 | #最大数#

最大数

1、题意重述

给定一个长度为n的数组nums，数组由一些非负整数组成，现需要将他们进行排列并拼接，每个数不可拆分，使得最后的结果最大，返回值需要是string类型，否则可能会溢出。

换句话说，就是给定一些元素，然后将这些元素拼接成一个最大的数。

2、思路整理

使用冒泡排序的思想：

Step1:在数组的第一位开始，依次比较相邻两位组成数值的大小，如果s[i]s[i+1] < s[i+1]s[i] 则调换s[i]和s[i+1]的位置。

Step2：在数组中从前往后重复Step1，最后得到答案。

3、代码实现

class Solution:
    def solve(self , nums ):
        s = nums
        for i in range(len(nums)):
            s[i] = str(s[i])
        for i in range(len(nums)):
            for j in range(len(nums)-i-1):
                a = str(nums[j])
                b = str(nums[j+1])
                if int("".join([b, a])) > int("".join([a, b])): #冒泡思想
                    s[j], s[j+1] = s[j+1], s[j]
        if s[0]=='0':
            return '0'
        return "".join(s)

4、复杂度分析

时间复杂度：两层循环，因此时间复杂度为$O(N^2)O(N^2)$。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为$O(1)O(1)$。