Question
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。
Solution
数字m和n,两种拼接方式mn和nm,因为长度都一样,所以可以用比较字符串的方式比较他们的大小。用快速排序,得到的第一个字符串表示和其他字符串的组合,它都需要放在前面才能使得组合的数字更小,所以它在排序的结果中位于第一个。(简单的证明)
Code
class Solution {
public:
static bool compare(const string& str1, const string& str2) {
return str1 + str2 < str2 + str1;
}
string PrintMinNumber(vector<int> numbers) {
vector<string> tb;
for (int i = 0; i < numbers.size(); i++) {
tb.push_back(to_string(numbers[i]));
}
sort(tb.begin(), tb.end(), compare);
string res = "";
for (int i = 0; i < tb.size(); i++) {
res += tb[i];
}
return res;
}
};