作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处
题目描述：
输入一个非负整数数组numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。
1.输出结果可能非常大，所以你需要返回一个字符串而不是整数
2.拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
数据范围:
0<=len(numbers)<=100
示例：
输入：
[11,3]
返回值：
"113"
解题思路：
本题考察算法思维。两种解题思路：
1)自定义sort比较方式
自定义sort函数中的比较方式，默认是两个数值比大小，这里是两个字符串叠加谁前谁后的问题。本质上就是另类排序题。
注意cmp函数定义在类中，需要加static转静态，或者放置在类外作为全局函数，如果不加static标识符，cmp函数就是普通成员函数，不满足sort函数中比较函数的类型要求。
该算法时间复杂度为O(nlog2n)，同快排复杂度。
2)冒泡排序
和解法一思路一样，只不过不采用STL的sort函数，自写冒泡排序。
该算法时间复杂度为O(n2)，同冒泡排序复杂度。
测试代码：
1)自定义sort比较方式
class Solution {
public:
// 重载排序比较
static bool cmp(string &s1, string &s2){
return s1 + s2 < s2 + s1;
}
// 输出最小数
string PrintMinNumber(vector<int>& numbers) {
string result = "";
// 判空
int size = int(numbers.size());
if(size == 0){
return result;
}
// 数字转字符串
vector<string> strs;
for(int i = 0; i < size; ++i){
strs.emplace_back(to_string(numbers[i]));
}
// 排序
sort(strs.begin(), strs.end(), cmp);
// 字符串组合
for(int i = 0; i < size; ++i){
result += strs[i];
}
return result;
}
};
2)冒泡排序
class Solution {
public:
// 输出最小数
string PrintMinNumber(vector<int>& numbers) {
string result = "";
// 判空
int size = int(numbers.size());
if(size == 0){
return result;
}
// 数字转字符串
vector<string> strs;
for(int i = 0; i < size; ++i){
strs.emplace_back(to_string(numbers[i]));
}
// 冒泡排序
for(int i = 0; i < size; ++i){
for(int j = 0; j < size - i - 1; ++j){
// 如果j叠加j+1比j+1叠加j要大，就把两者换个顺序
string s1 = strs[j] + strs[j + 1];
string s2 = strs[j + 1] + strs[j];
if(s1 > s2){
swap(strs[j], strs[j + 1]);
}
}
}
// 字符串组合
for(int i = 0; i < size; ++i){
result += strs[i];
}
return result;
}
};
