解题 | 最大数（C++版本）

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

方法一：暴力破解法
题目分析：
由描述中分析可得，解决这个问题主要分为三步走：

• 排序（核心问题）
• 拼接
• 非负整数到string类型的转换

插入一个图片，可以一目了然。

解决办法：
首先从以上三个问题中最简单的说起：
1.非负整数到string类型的转换
最简单的办法：

std::string to_string(int value);

同时，还可以考虑C的库函数：

int sprintf( char *buffer, const char *format [, argument] ... );

（不过需要自行定义buffer）
2.拼接问题
对于string类型来说，最普遍的使用就是“+”，或者还可以考虑append()方法。
3.排序（重点）
根据描述中要得到最大的结果来看，首先我们想到的是越高位的值越大，这个最终的值就会越大。那么问题在于，排序中怎么按照高位从大到小的顺序排序，哎~是不是想到了sort()这个排序函数！
由于sort()函数默认为是升序排序，所以这里我们一定要编写排序规则函数compare使sort函数降序排序。
综上所述，目前我们的代码可以这样写：

class Solution {
public:
    /**
     * 最大数
     * @param nums int整型vector
     * @return string字符串
     */
     //排序规则函数
    static bool compare(string& a, string& b)
    {
        return a + b > b + a;
    }

    string solve(vector<int>& nums) {
        if (nums.size() == 0) return nullptr;
        vector<string> strs;
        //将输入的非负整型数转化为string类型
        for (auto c : nums)
        {
            strs.push_back(to_string(c));
        }

        //排序
        sort(strs.begin(), strs.end(), compare); 

        //拼接
        string MaxNum;
        for (auto c : strs)
        {
            MaxNum += c;
        }

        //类似["0","0"]的输入，输出是"0"而不是"00"，
        //所以一定要在第一个元素为"0"时直接输出"0"
        if (MaxNum[0] == '0') return "0";

        return MaxNum;
    }
};

当然，不能使用如下的函数：

bool compare(string& a,string& b)
{
    return a>b;
}

因为：假设两个数207和88，使用这个排序规则函数，会将207放在88之前，但是显然88207>20788。

复杂度分析：

• 时间复杂度：两个for循环的时间复杂度都为 ，sort函数采用的是改进的快排，时间复杂度也为 ，所以本段代码的时间复杂度为 ;
• 空间复杂度：因为申请了一个存放转换后元素的vector，所以空间复杂度为 。

方法二：vector+桶排序
那么问题来了！如果想降低时间复杂度该怎么做呢，典型的就是用空间换取时间，我们可以使用桶排序的思想，定义一个vector数组，存放对应最高位的值。
动图演示如下：

代码如下：

class Solution {
public:
    /**
     * 最大数
     * @param nums int整型vector
     * @return string字符串
     */
     //排序规则函数
    static bool compare(string& a, string& b)
    {
        return a + b > b + a;
    }

    string solve(vector<int>& nums) {
        if (nums.size() == 0) return nullptr;

        //使元素按照最高位的值分类
        vector<string> strsArray[10]; 
        for (auto& c : nums)
        {
            string temp = to_string(c);
            int index = temp[0] - '0';
            strsArray[index].push_back(temp);
        }

        string MaxNum;
        for (int i = 9; i >= 0; i--)
        {
            //如果该vector没有元素直接跳过，如果只存在一个元素则不需排序
            if (strsArray[i].size() == 0) continue;
            if (strsArray[i].size() > 1)
                sort(strsArray[i].begin(), strsArray[i].end(), compare);
            for (auto& c : strsArray[i])
                MaxNum += c;
        }

        //类似["0","0"]的输入，输出是"0"而不是"00"，
        //所以一定要在第一个元素为"0"时直接输出"0"
        if (MaxNum[0] == '0')
        {
            MaxNum = '0';
        }

        return MaxNum;
    }
};

复杂度分析：

• 时间复杂度：相比第一种算法而言，减少了最高位值不同元素的比较时间，如果输入的数据最高位均不同，那么此时的时间复杂度为，但是平均时间复杂度并没有改变，仍为 。
• 空间复杂度：修改后的代码看似多申请了很多vector，但是总的来说存储的元素的数量没有变，所以此时空间复杂度仍为为 。