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

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

样例

1
2
3

输入：[3, 32, 321]

输出：321323

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

定理证明

离散数学的 定理：

  1. 反对称性
  2. 传递性
  3. 自反，反自反

在一个集合 $R$ 中， 有 <$1,2$> 属于 R ， 一定也存在 <$2,1$> 属于R ，

这个就是对称性

举个例子：

$a<=b$ $=> $ $b>=a$

这个就是一个对称性

传递性举例： $$ a<=b, b<=c\ 可以得到:\

a<=c $$

反对称性 $$ (\overline{ab}<=\overline{ba}) \and ( \overline{ ba }<= \overline{ab}) 可以得到: \ \overline{ab}=\overline{ba} $$ 因此 字典序 里面 一定会满足 反对称性

离散数学教程

如果关系满足 反对称性 和 传递性，那么集合内的元素都是可以进行排序的，具有全序关系

这里的思路是定义了新的二元运算，a <= b 等价于 ab <= ba，然后去证明这个比较运算可以得到最小字符串，以及该运算是全序关系，可以排序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    string printMinNumber(vector<int>& nums) {
        if(nums.size() == 0) return "";
        vector<string> a;
        for(int u:nums) a.push_back(to_string(u));
        
        sort(a.begin(),a.end(), cmp);
        string res;
        for(auto v: a) res+=v;
        return res;
    }
    
    static bool cmp(string a,string b) {
        return a+b < b+ a;
    }
    
    
};