题目描述

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

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

数据范围

数组长度 [0,500]。

样例

输入：[3, 32, 321]
输出：321323
• 1
• 2
• 3

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

方法一：字符串排序 O(nlogn)

这题我们可以发现一个规律，可以通过判断拼接后的字符串的大小来进行排序，假定有字符串 x 和 y ：

如果 x+y > y+x ，则 x “大于” y ，即 x 排在 y 的后面。

如果 x+y < y+x ，则 x “小于” y ，即 x 排在 y 的前面。

注意： 上述的加法运算并不是实际意义上的整数加法运算，而是字符串的拼接。当然，大于小于也不是整数的大小比较，而是指排序的规则。

例如 x = 3 且 y = 32 ，可以发现：

x + y = 332 > y + x = 323 ，所以我们认为 x “大于” y ，即 x 要排在 y 的后面。

故通过上述规则对数组中的所有字符串进行排序，然后再将排序后的数组中的字符串拼接起来得到的字符串一定是最小的。

class Solution {
public:
    string printMinNumber(vector<int>& nums) {
        vector<string> str;
        for (int i = 0; i < nums.size(); i++)
            str.push_back(to_string(nums[i]));
        sort(str.begin(), str.end(), [](string& x, string& y) {return x + y < y + x; });
        string res;
        for (int i = 0; i < str.size(); i++)
            res += str[i];
        return res;
    }
};

欢迎大家在评论区交流~