目录
力扣179. 最大数
难度 中等
给定一组非负整数 nums
,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。
注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。
示例 1:
输入:nums = [10,2] 输出:"210"
示例 2:
输入:nums = [3,30,34,5,9] 输出:"9534330"
提示:
1 <= nums.length <= 100
0 <= nums[i] <= 10^9
class Solution {
public:
string largestNumber(vector<int>& nums) {
}
};
解析代码1_仿函数
贪心策略:按照题目的要求,重新定义一个新的排序规则,然后排序即可。
排序规则:
- 「A 拼接 B」 大于 「B 拼接 A」,那么 A 在前,B 在后。
- 「A 拼接 B」 等于 「B 拼接 A」,那么 A B 的顺序可以任意。
- 「A 拼接 B」 小于 「B 拼接 A」,那么 B 在前,A 在后。
class Solution {
struct cmp
{
bool operator()(int a, int b)
{
string str1 = to_string(a);
string str2 = to_string(b);
return str1 + str2 > str2 + str1;
}
};
public:
string largestNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), cmp());
string ret;
for(auto& e : nums)
{
ret += to_string(e);
}
return ret[0] == '0' ? "0" : ret; // 去掉前导0
}
};
解析代码2_Lambda
贪心策略在上面讲了,用Lambda简化下代码:
class Solution {
public:
string largestNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), [](int a, int b)
{
string str1 = to_string(a);
string str2 = to_string(b);
return str1 + str2 > str2 + str1;
}
);
string ret;
for(auto& e : nums)
{
ret += to_string(e);
}
return ret[0] == '0' ? "0" : ret; // 去掉前导0
}
};