剑指offer 46. 把数组排成最小的数

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：剑指offer系列题解
📝原题地址：题目地址
📣专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

题目描述

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

例如输入数组 [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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

欢迎大家在评论区交流~