c++用贪心算法写给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。 说明:输出结果可能非常大,所以Jim需要返回一个字符串而不是整数
时间: 2024-02-21 16:00:32 浏览: 66
好的,这个问题也可以使用贪心算法来解决。我们可以首先将 nums 数组中所有的数字转化为字符串,然后对它们进行排序。
排序的依据是:如果将字符串 a 和字符串 b 拼接起来得到 ab,将字符串 b 和字符串 a 拼接起来得到 ba,如果 ab 大于 ba,则认为 a 大于 b。这是因为我们希望拼接后的整数尽可能大,而将较大的数字放在前面可以得到更大的整数。
排序完成后,我们只需要将所有的字符串拼接起来即可得到最终的结果。
以下是示例代码(使用 C++ 实现):
```c++
class Solution {
public:
string largestNumber(vector<int>& nums) {
// 将所有数字转化为字符串
vector<string> strs;
for (int num : nums) {
strs.push_back(to_string(num));
}
// 对所有字符串进行排序
sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
return a + b > b + a;
});
// 拼接所有字符串并返回结果
string ans = "";
for (const string& str : strs) {
ans += str;
}
// 特判输出结果为 0 的情况
if (ans[0] == '0') {
return "0";
}
return ans;
}
};
```
需要注意的是,在比较字符串大小时,我们使用了一个匿名 lambda 函数,它的实现方式与上面的比较函数类似。另外,为了方便,我们将所有数字先转化为字符串。
阅读全文