Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9]
, the largest formed number is 9534330
.
Note: The result may be very large, so you need to return a string instead of an integer.
问题:给定一个数组,求将数组元素拼凑成一个值最大的整数。
将整型数组的转化为字符串数组,用 std::sort 对字符串数组排序,使得排序后元素直接连接成为最大值整数。
使用默认的比较函数排序,会得到不一定是最大值,例如 {360, 36} 排序后得到的是 36036 ,明显不是小于 36360。解决这个问题,就是重写比较函数,使得排序后的两个元素连接成为较大的整数即可,很简洁。
int static comp(string s1, string s2){
return (s1 + s2) > (s2 + s1);
} string largestNumber(vector<int>& nums) {
vector<string> numsStr;
for (int i = ; i < nums.size(); i++) {
numsStr.push_back(to_string(nums[i]));
} std::sort(numsStr.begin(), numsStr.end(), comp); string res = "";
for (int i = ; i < numsStr.size(); i++) {
res += numsStr[i];
} int i = ;
while (i < res.size()- && res[i] == '') {
i++;
}
res = res.substr(i); return res;
}