题目描述

剑指 Offer 45. 把数组排成最小的数

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

示例 1:

输入: [10,2]
输出: "102"

示例 2:

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

提示:

• 0 < nums.length <= 100

说明:

• 输出结果可能非常大，所以你需要返回一个字符串而不是整数
• 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

算法描述

本题本质为排序问题，即按本题要求所约束的 「比较规则」 比较 nums 中各数字的大小，从小到大排列后拼接结果即为所求。这里的比较规则不再是数值比较，而是如下 。

首先我们约定如下:

• \(<\) 符号表示数值比较的「小于」，\(<'\)表示本题比较规则的「小于」。
• \(x,y\) 为数字字符串。\(|x|,|y|\)为其数值大小。
• \(xy\) 表示数字字符串 \(x\) 与 \(y\) 拼接后的数字字符串，\(|xy|\) 表示其数值大小。

【本题比较规则】

将 nums 中的两个数 \(x,y\) 视作字符串后拼接得到\(xy\) 和 \(yx\) 。

• 若 \(|xy|<|yx|\)，则称 \(x\) 小于\( y\) ，记作 \(x<'y\)。
• 若 \(|xy|>|yx|\) ，则称 \(y \)小于 \(x\) ，记作 \(y<'x\)。
• 若 \(|xy|=|yx|\)，则称 \(x\) 等于 \(y\)，记作 \(x='y\)。

例如 \(|x|=3,|y|=30∣x∣=3,∣y∣=30\) ，，因为 \(330>303\) 更大，则在这个比较规则下 \(y<'x\)。

以 nums = [3,30,34,5,9] 为例，可以两两比较得到在本题比较规则小的大小 "30" <' "3" <' "34" <' "5" <' "9"，因此答案为 "3033459" 。

最优子结构

上述规则之所以正确，是因为它具有传递性。就像数值比较中 \(1<2,2<3\)的情况下，一定有 \(1<3\) ，否则比较规则不能成立。要证明有传递性，即证明对于数字 \(x,y,z\) 在上述规则下有 \(x<'y,y<'z\)，则在同一规则下必有 \(x<'z\)。

设十进制数 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 ，传递性证毕

更关键的问题是， 为什么本题规则之下从小到大排序后的结果拼接的数字是最小的？

贪心选择性

采用反证法证明，即令 \(A\)是按照本题比较规则得到的升序排列构成的字符串，假设 存在排列 \(B\) ，使得 \(|B|<|A|\) ，下面我们来推翻此假设。再次强调，后续说明中的「序」、「大小」、「最大」等都是本题比较规则下的表述。

1. \(B\) 可通过有限次相邻「逆序对」的交换得到 \(A\) ，且交换次数是「逆序对」的数量 (逆序数)。

可以这么思考，在 \(B\) 中找到当前最大数 m ，m 右侧的数都与 m 构成一个逆序对，通过「冒泡」的方式将 m 交换到最右侧。然后将剩下的数中最大者按照同样的方式交换到最右侧 (m 的前一位) ，重复此操作直到无逆序对，则 \(B\) 变为 \(A\) 。交换次数显然为逆序数。

2. 对于 \(A\) ，交换任意两个相邻元素 \(a,b\)(\(a<'b\)) 的位置得到排列 \(C\) ，则必有 \(|A|<|C|\)。

将相邻的 \(a\) 与 \(b\) 交换，\(ab\) 变为 \(ba\) ，其左右侧的「数字字符串」对应的「数值」不变，但\( |ab|<|ba|\)，因此 \(|A|<|C\)。

3. 对于 \(A\) ，交换任意两个元素 \(a,b\) (\(a<'b\)) 位置得到排列 \(C\) ，则必有 \(|A|<|C|\)。

当这两个元素相邻时，为推论2。若 \(a,b\) 不相邻 ，例如 \(axyzb\) ，则交换 \(a,b\) 相当于依次交换 \(ax,ay,az\) ，接着交换 \(za,zb,yb,xb\) 。根据推论2，每一次相邻交换都使得交换后的值更大，因此 \(|A|<|C|\)。

4. \(|A|<|B|\) 。

根据推论1， \(B\) 通过交换相邻元素得到 \(A\) 的逆过程，就是 \(A\) 通过交换相邻元素得到 \(B\) 的过程，且在这个过程中交换的 \(x\) 和 \(y\) ( \(x\) 在 \(y\) 的左侧) 均满足 \(x<'y\)，因此从 \(A\)到\(B\)的过程的每一次交换，都使得交换后的排列对应的数值更大，因此 \(|B|>|A|\)。

假设不成立，即不存在数值更小的 \(B\) 排列，所以 \(A\) 一定是数值最小的排列。

代码

class Solution {
public:
    string minNumber(vector<int>& nums) {
        auto cmp = [](const int& a, const int& b){
            string res1 = to_string(a)+to_string(b);
            string res2 = to_string(b)+to_string(a);
            return res1 < res2;
        };
        sort(nums.begin(),nums.end(),cmp);
        string res;
        for(auto num:nums){
            res += to_string(num);
        }
        return res;
    }
};