【剑指Offer-45】把数组排成最小的数

问题

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

示例

输入： [3,30,34,5,9]
输出： "3033459"

解答

class Solution {
public:
    string minNumber(vector<int>& nums) {
        string res;
        vector<string> strs;
        for (auto i : nums)
            strs.push_back(to_string(i));
        sort(strs.begin(), strs.end(), [](const auto& s1, const auto& s2) {
            return s1 + s2 < s2 + s1;
        });
        for (auto s : strs)
            res += s;
        return res;
    }
};

重点思路

本题的要点是对输入的数组按照题目要求自定义排序。自定义排序只需要记住，当return为true时，s1排在s2前面就行。该自定义条件直观上很容易想到，因为题目要求的就是字符串组成的值最小，那么我们就需要让能组成较小值的元素排在最前面，自定义排序实现了这个功能。

这里还需要注意的是，需要证明xy < yx，yz < zy时，xz < zx，即传递性。这里引用一下题解里的证明：

字符串 xy < yx , yz < zy ，需证明 xz < zx 一定成立。

设十进制数 x, y, z 分别有 a, b, c 位，则有：
（左边是字符串拼接，右边是十进制数计算，两者等价）
xy = x * 10^b + y 
yx = y * 10^a + x

则 xy < yx 可转化为：
x * 10^b + y < y * 10^a + x
x (10^b - 1) < y (10^a - 1)
x / (10^a - 1) < y / (10^b - 1)     ①

同理， 可将 yz < zy 转化为：
y / (10^b - 1) < z / (10^c - 1)     ②

将 ① ② 合并，整理得：
x / (10^a - 1) < y / (10^b - 1) < z / (10^c - 1)
x / (10^a - 1) < z / (10^c - 1)
x (10^c - 1) < z (10^a - 1)
x * 10^c + z < z * 10^a + x
∴  可推出 xz < zx ，传递性证毕

【剑指Offer-45】把数组排成最小的数

原文：https://www.cnblogs.com/tmpUser/p/14485060.html