一、题目描述
力扣链接:力扣179.最大数
给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。
注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。
示例 1:
输入:nums = [10,2]
输出:“210”
二、C++题解
可使用贪心策略,只要每一步都保证是最大的,那么最后拼接出来的数字一定是最大的。
有两个推论:文章来源:https://www.toymoban.com/news/detail-804419.html
- 两个数字拼接,若
x+y > y+x
,则拼接时x应在前; - 反之,y应该在前。
因此,算法流程为:文章来源地址https://www.toymoban.com/news/detail-804419.html
- 初始化: 字符串列表 strs ,保存各数字的字符串格式。
- 列表排序: 根据贪心策略对 strs 进行从大到小排序。
- 返回值: 拼接 strs中的所有字符串,并返回。
class Solution {
public:
string largestNumber(vector<int>& nums) {
vector<string> strs;
string result;
if (nums.empty()) {
return result;
}
// 把所有数字转为字符串并存储为数组
for (auto& num : nums) {
strs.push_back(to_string(num));
}
// 按从大到小排序
sort(strs.begin(), strs.end(), [](string& x, string& y){
return x + y > y + x;
});
// 如果排完最大的是0,那么直接输出0,避免输出“000...”
if (strs[0] == "0") {
return "0";
}
// 直接将数组中的字符串拼接起来
for (auto& str : strs) {
result.append(str);
}
return result;
}
};
到了这里,关于【算法详解】力扣179.最大数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!