难度中等583
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"示例 2:
输入: [3,30,34,5,9]
输出: "3033459"提示:
0 < nums.length <= 100
说明:
- 输出结果可能非常大，所以你需要返回一个字符串而不是整数
- 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
解题思路：
此题求拼接起来的最小数字，本质上是一个排序问题。设数组 nums 中任意两数字的字符串为 x 和 y，则规定排序判断规则为：
- 若拼接的字符串
x+y < y+x，说明 x 应该排在 y 后面 - 若拼接的字符串
x+y > y+x，说明 x 应该排在 x 前面
举个例子，比如说数组为 [“30”, “3”, “25”, ...]，这里 x 代表 “30”，y 代表 “3”，那么 “303” < “330” 的，也就是 x+y < y+x，说明 x 是排在 y 的后面的，以此类推！
为了使用这个结论，我们必须验证这个结论具有传递性，下面是证明（转载的）：
字符串 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 ，传递性证毕 接着就是实现代码，我们这里举两个实现方法，一个是使用快速排序，一个是使用仿函数：
1、仿函数
struct Compare
{
bool operator()(const string& x, const string& y)
{
return x + y < y + x;
}
};
class Solution {
public:
string minNumber(vector<int>& nums) {
string tmp;
vector<string> other; // 存放将nums转化为字符串的数组
for(int i = 0; i < nums.size(); ++i)
other.push_back(to_string(nums[i]));
// 调用sort，其中仿函数自己写（也可以写成lambda）
sort(other.begin(), other.end(), Compare());
for(int i = 0; i < nums.size(); ++i)
tmp += other[i];
return tmp;
}
};2、快速排序
我们需要修改一些排序中的细节，所以我们需要自己写一个快排！
class Solution {
public:
string minNumber(vector<int>& nums) {
string tmp;
vector<string> other; // 存放将nums转化为字符串的数组
for(int i = 0; i < nums.size(); ++i)
other.push_back(to_string(nums[i]));
// 调用sort，其中仿函数自己写（也可以写成lambda）
quick_sort(other, 0, other.size() - 1);
for(int i = 0; i < nums.size(); ++i)
tmp += other[i];
return tmp;
}
private:
void quick_sort(vector<string>& v, int left, int right)
{
if(left >= right)
return;
int tmpL = left;
int tmpR = right;
while(tmpL < tmpR)
{
// 从右边找小的
while(tmpL < tmpR && v[tmpR]+v[left] >= v[left]+v[tmpR])
tmpR--;
// 从左边找大的
while(tmpL < tmpR && v[tmpL]+v[left] <= v[left]+v[tmpL])
tmpL++;
swap(v[tmpL], v[tmpR]);
}
swap(v[left], v[tmpL]);
quick_sort(v, left, tmpL - 1);
quick_sort(v, tmpL + 1, right);
}
};
