其实这道题，大概看完就知道是一个排序的问题，无非就是数组中的元素以一个合适的位置排好序，这样从头加到尾，组成的整体数字最小！(题目中也暗示你排序问题了)
个人捉摸了一会，这道题能很好地锻炼仿函数的编写规则和库函数sort()的配套使用，还有就是巧妙地字符串操作和贪心思想，因此将它记录;
解题思路
核心: 怎么确定元素a，b的先后顺序？
贪心思想: 先将a，b两数字转成string，之后如果a+b<b+a**，那么**a就排在b前面，以此类推；
最终将排好序的每个数组转string全部从头到尾按顺序拼接即可;
实现代码
#include <string>
class Solution {
public:
class cmp{
public:
bool operator()(int a,int b)
{
//先分别转正string
string sa = to_string(a);
string sb = to_string(b);
return sa+sb<sb+sa;
}
};
string PrintMinNumber(vector<int> numbers) {
//处理空串
if(numbers.size()==0) return "";
//按照贪心仿函数规则，调用sort
sort(numbers.begin(),numbers.end(),cmp());
//依次拼接最终答案
string ret;
for(auto&e:numbers){
ret+=to_string(e);
}
return ret;
}
};
这里要注意的点是我们调用库函数sort()，那么注意他的仿函数比较大小的规则:
源码如下:
less<int>递增,如1,2,3,4,5: 仿函数源码: return a<b;
greater<int>递减,如5,4,3,2,1: 仿函数源码: return a>b;
调用sort()想要递增or递减完全是按照大于号或者小于号的方向指示的;
可万一面试官突然不让你算法sort()函数了呢?不慌，贪心思想都想出来了，无非就是手撕一个排序嘛，量元素比较的时候套用我们的贪心思想比较即可!
实现代码
class Solution {
public:
string PrintMinNumber(vector<int> numbers) {
//处理空串
if(numbers.size()==0) return "";
string res;
//冒泡排序
for(int i = 0; i < numbers.size() - 1; i++){
for(int j = 0; j < numbers.size() - i - 1; j++){
//数字转string好贪心处理
string s1 = to_string(numbers[j]);
string s2 = to_string(numbers[j+1]);
//贪心比较拼接的大小交换位置
if(s1+s2 > s2+s1)
swap(numbers[j], numbers[j + 1]);
}
}
//字符串叠加返回
for(int i = 0; i < numbers.size(); i++)
res += to_string(numbers[i]);
return res;
}
};
这样写法我们就不用注意sort()库函数里的大于小于号的方向了，万全按照自己的逻辑进行比较即可，可以看到，我们交换时采用的是s1 > s2,而sort()方法中使用的则是<，这是因为人家sort()内部有自己的传参和比较的逻辑，我们不必太纠结，知道怎么正确用它就好！
这题的关键是贪心，可以好好品味字符串的魅力，不让用sort(),那可以手撕排序，比如冒泡，快排都往上写，尽情秀你的代码能力!