```
/*
Main idea: sort the input so that a sequential concatentation will provide the largest number.
Comparison approximately follows the string comparison (from higher digit to lower digit).
The only exception is like "12" and "12X" (X can be any number of any non-zero length).
String comparison regards "12X" as larger because '\0' is smaller then any number charactor, but in this problem only when X is "larger" than "12", "12X" can be considered larger then "12".
That is because "12X12" is larger than "1212X" only when "X12" is larger "12X".
Optimization:
Comparing "X12" and "12X" is equivalent to comparing "X" and "12".
Because when X<12 or X>12 (this < and > are the comparison for this problem), "X12" < "12X" or > correspondingly.
And when X=12 (in this problem "1212"="12"), "X12"="12X".
*/
class Solution {
//return whether lth is larger than rth
static bool cmp(const string& lth,const string& rth){
//CASE 1, normal string comparison
if(lth.size()==rth.size())
return lth.compare(rth)>0;
int res=0;
size_t min_size=min(lth.size(),rth.size());
if(lth.size()<rth.size())
res=-rth.compare(0,min_size,lth);
else
res=lth.compare(0,min_size,rth);
if(res!=0)
return res>0;
//CASE 2, rear comparison
if(lth.size()>rth.size()){
return cmp(lth.substr(min_size),rth);
}else{
return cmp(lth,rth.substr(min_size));
}
}
public:
string largestNumber(vector<int> &num) {
vector<string> arr;
arr.reserve(num.size());
for(int v:num){
//arr.push_back(to_string(v));//for speed
char temp[30];
sprintf(temp,"%d",v);
arr.push_back(temp);
}
sort(arr.begin(),arr.end(),cmp);
if(arr.empty() || arr[0]=="0")
return "0";
string res;
res.reserve(num.size()*arr[0].size()*2);
for(string& v:arr)
res+=move(v);
return res;
}
};
```