跟着姚桑学算法-把数组排成最小的数

题. 把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

例如输入数组 [3,32,321]，则打印出这 3 个数字能排成的最小数字 321323。

数据范围
数组长度 [0,500]。

样例

输入：[3, 32, 321]

输出：321323

注意： 输出数字的格式为字符串。

【题解】--- 比较器

由于输出要是string格式，所以要在将nums的元素放入str的时候，可以使用to_string()函数；
又因为是vector，所以排序是sort(a.begin(), a.end())。
如果想把cmp放在里面，一定要加static关键字，同时 注意 返回类型是bool。

复杂度分析：

由于方案种类是组合数的方式，所以方案数就是n的阶乘。
即O(n!)。

C++代码实现：

class Solution {
public:
    static bool cmp(string a, string b)  // **1 **2
    {
        return a + b < b + a;
    }
    string printMinNumber(vector<int>& nums) {
        vector<string> str;
        for(auto x : nums) str.push_back(to_string(x)); // **3
        sort(str.begin(), str.end(), cmp); // **4

        string res = "";
        for(auto s : str) res += s;
        return res;
    }
};