思路：

题目的主要信息：

• 对非负整数进行拼接，使得到数最大
• 得到的数可能会很大，需要用string保存

我们可以想到，对于一个数列拼接，自然是拼接后在前面数在数组前方比较好，这就涉及到了一个排序，如何排序：自然是顺序拼接较大的放在前面，将int转换成string后相连，然后比较字典序即可。

方法一：冒泡排序法

具体做法：

使用冒泡排序法，依次比较前后两个数，转化成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。去掉重复的0
            return "0";
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O\left(n^2\right)O(n^2)$O(n2)，冒泡排序两层循环
• 空间复杂度：$O\left(1\right)O(1)$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\left(nlo{g}_{2}n\right)O(nlog\_2n)$O(nlog2​n)，sort函数属于快排，复杂度为O(n)
• 空间复杂度：$O\left(1\right)O(1)$O(1)，没有使用额外的空间