给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。 说明:输出结果可能非常大,用c++输出,所以Jim需要返回一个字符串而不是整数。
时间: 2023-06-27 08:04:28 浏览: 108
这个问题可以使用字符串排序的方法来解决。具体来说,我们需要把每个数都转换为字符串,然后按照以下规则进行排序:
对于任意两个数 a 和 b,如果将它们都转换为字符串后,得到的字符串 ab 和 ba 拼接起来的结果 ab > ba,那么应该将 a 排在 b 的前面。
比如说,对于两个数 9 和 34,由于在字符串的拼接结果中 934 > 349,因此应该把 9 排在 34 的前面。
排序完成后,我们将每个数按照顺序依次拼接起来,就得到了最大的整数。
下面是一个 C++ 实现的例子:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
bool cmp(string a, string b) {
return a + b > b + a;
}
string largestNumber(vector<int>& nums) {
vector<string> strs;
for (int num : nums) {
strs.push_back(to_string(num));
}
sort(strs.begin(), strs.end(), cmp);
if (strs[0] == "0") {
return "0";
}
string ans;
for (string str : strs) {
ans += str;
}
return ans;
}
int main() {
vector<int> nums = {3, 30, 34, 5, 9};
string ans = largestNumber(nums);
cout << ans << endl; // 输出 "9534330"
return 0;
}
```
在这个实现中,我们首先将每个数都转换为字符串,并将它们存放在一个 vector<string> 中。然后我们定义了一个比较函数 cmp,用于在排序时比较两个字符串的大小关系。最后我们使用 sort 函数对字符串数组进行排序,并将排序后的结果依次拼接起来,返回最终的答案。
需要注意的一点是,如果排序后最大的字符串是 "0",那么我们应该直接返回 "0",而不是 "00" 或者其他以 "0" 开头的字符串。
阅读全文