Compose the largest number out of a set of integers. The set of integers can be more than 1 digit.
Since the numbers can be more than one digit, using greedy algorithm and sorting them in descending order wont help. Eg: Input : 21 and 2 , Sorting in descending would give an answer 212 which is wrong since the 221 > 212
I decided to come up with the following algorithm: I have a vector of strings as input so I use the std::sort function with a custom function to sort it.
If I have two strings i = "21" and j ="2", I concatenate i,j and j,i and then compare the result
bool isGreater(string i,string j){
string a = i+j;
string b = j+i;
return a >= b;
}
string largest_number(vector<string> a) {
string result =" ";
sort (a.begin(),a.end(),isGreater);
for(int i =0; i<a.size(); i++){
result+=a[i];
}
return result;
}
It works for some cases but I fail a few test cases and get the message:
stderr: terminate called after throwing an instance of 'std::logic_error' what(): basic_string::_M_construct null not valid
Appreciate any help.
Aucun commentaire:
Enregistrer un commentaire