方法：排序
解题思路
- 将数字转化为字符串数组，然后 \(sort()\)；
cmp()函数
static bool cmp(string a, string b) {
return a + b < b + a;
}
代码
// 写法一
class Solution {
public:
static bool cmp(string a, string b) {
return a + b < b + a;
}
string minNumber(vector<int>& nums) {
int n = nums.size();
vector<string> dp(n);
for (int i = 0; i < n; i ++ ) dp[i] = to_string(nums[i]);
sort(dp.begin(), dp.end(), cmp);
for (int i = 1; i < n; i ++ ) dp[i] = dp[i - 1] + dp[i];
return dp[n - 1];
}
};
// 写法2，较慢
class Solution {
public:
static bool cmp(int a, int b) {
return to_string(a) + to_string(b) < to_string(b) + to_string(a);
}
string minNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), cmp);
string ans;
for (int i = 0; i < nums.size(); i ++ ) ans += to_string(nums[i]);
return ans;
}
};
复杂度分析
时间复杂度：\(O(nlogn)\)；
空间复杂度：写法一：\(O(n)\)，写法二：\(O(1)\)，忽略排序时的调用栈。