问题

给定一个整数数组，把他们排成最小的数，用字符串形式返回该数

算法：拼接排序

容易想到，我们希望高位数小的在数组靠前面。但是难点在于怎么做到。

然而，高位数小的排前面这个规则难以实现，因为每个数的位数可能不一样。

实际上，考虑更直接的问题：两个数a, b怎么拼形成的数最小？拼的方式实际只有两种: a + b / b + a。我们要将所有拼接方案中结果最小的放在数组靠前位置。

所以只需要按照这个规则排序即可：两个数，按照拼接方案中结果最小的那个拼接方案排序，这样形成的数就是最小的（严禁证明可参考lc题解）

复杂度

时间：$O(NlogN)$, N为最终返回的字符串长度
空间：$O(N)$

代码

class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> num_strs;
        for(auto x: nums) num_strs.push_back(to_string(x));
        sort(num_strs.begin(), num_strs.end(), [](string &a, string &b){return a+b < b+a;});
        string res;
        for(auto s: num_strs){
            res += s;
        }

        return res;
    }
};