题解 | #最大数#

题目描述
给定一个数组由一些非负整数组成，现需要将他们进行排列并拼接，使得最后的结果最大，返回值需要是string类型否则可能会溢出

方法一：暴力求解之冒泡排序解法

求解思路
对于本题，我们想到排序规则：顺序拼接较大的字符放在前面，将int转换成string后相连，然后比较字典序即可。对于在比较大小时，我们举“30”，“1”这个例子，我们可以将其拼接为301或者130这两种情况，此时只需要比较两个数值的大小即可，即301大于130，所以排序301，其他情况如上进行。最后在暴力解法中，我们使用冒泡排序法，依次比较前后两个数，转化成string后进行拼接。

图片说明

解题代码

class Solution {
public:
    string solve(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++)
        { //暴力解法之冒泡法
            for(int j = 1; j < nums.size(); j++)
                if(to_string(nums[j]) + to_string(nums[j - 1]) > to_string(nums[j - 1]) + to_string(nums[j]))
                {
                    int temp = nums[j];//常规的交换次序的语句
                    nums[j] = nums[j - 1];
                    nums[j - 1] = temp;
                }                    
        }
        //小细节处理如下
        string res = "";
        for(int i = 0; i < nums.size(); i++)  //遍历排序后的数组
            res += to_string(nums[i]);
        if(res[0] == '0')   //当第一位数就是0时，去掉重复的0
            return "0";
        return res;
    }
};

复杂度分析
时间复杂度：冒泡排序的时间复杂度，为 $图片说明$
空间复杂度：没有引入新的内存地址空间，空间复杂度为 $O(1)$

方法二：优化解法--重载sort函数

求解思路
对于本题目我们可以重载sort函数的排序规则，其规则更改为：将两数转变成string后，相加比较大小。

图片说明

解题代码

class Solution {
public:
    static bool comp(int s1, int s2)
    {  //新规则：转化成字符串以后再比较相加
        return to_string(s1) + to_string(s2) > to_string(s2) + to_string(s1);
    }
    string solve(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end(), comp);
        string res = "";
        for(int i = 0; i < nums.size(); i++)  //遍历排序后的数组
            res += to_string(nums[i]);
        //小细节处理
        if(res[0] == '0')   //当第一位数就是0时，整个最大也为0。去掉重复的0
            return "0";
        return res;//返回结果
    }
};

复杂度分析
时间复杂度：快排的时间复杂度，只是修改了比较的规则，为 $O(nlogn)$ 。
空间复杂度：同时考虑到快排的最坏情况，其空间复杂度为 $O(N)$ 。