Largest Number
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.
-------------------------------------------------- thinking --------------------------------------------------
edges cases:
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[803, 8038]
[308, 3083]
This is a problem about sorting by constructing your own comparing function. The only
difficulty is how to get a right and efficient comparing function, then you are down.
---------------------------------------------- problems ----------------------------------------------------
1. run time fail for edge case [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
Here we want a decreasing order sort, so the equal situation in cmpr_func, the status
should return false. After modifying it, the run time problem disappears. Honestly, I don't
know the reason here.
2. Using revert number vector to record reverted number
This is a wasting step. You need to use additional array to record them, and there are
additional cycles to do reverting and comparing. We should compare two numbers directly
There are several ways to do this comparing step:
- to_string(a) + to_string(b) > to_string(b) + to_string(a)
- get bit size of a and b, and constructing comparing numbers ab > ba: the problem for this method is the overflowing for numbers
- get bit size of a and b, and comparing firstly a vs b+front_part(a), then if equal, b vs end_part(a) (the thing we need to pay attention here is the second part, where b should be on the left!
------------------------------------------------------------- codes ------------------------------------------
class Solution {
public:
string largestNumber(vector<int> &num) {
//do not using rvt_num to record reverted arrays, we can compare directly
//vector<int> rvt_num(num);
//for (int i = 0; i < num.size(); i++) {
// rvt_num[i] = num_rvt(num[i]);
//}
std::sort(num.begin(), num.end(), num_cmp);
//print result
string result = "";
if (num[0] == 0) {
return "0";
}
for (int i = 0; i < num.size(); i++) {
result += std::to_string(num[i]);
}
return result;
}
static bool num_cmp(int num1, int num2) {
if (num1 == num2) {
return false;
}
if (num1 == 0) {
return false;
}
if (num2 == 0) {
return true;
}
int bit1 = log10(num1);
int bit2 = log10(num2);
if (bit1 == bit2) {
if (num1 > num2) {
return true;
} else {
return false;
}
// this is the part of using method 2, but it will slow the run time performance
// I think the main reason is the test cases are causing larger than 9, so we spend longer time on the if condition here
//} else if (bit1 + bit2 <= 9) {
// int new_num1 = num1 * pow(10, bit2 + 1) + num2;
// int new_num2 = num2 * pow(10, bit1 + 1) + num1;
// if (new_num1 > new_num2) {
// return true;
// } else {
// return false;
// }
} else {
bool swi = false;
if (bit1 < bit2) {
swi = true;
int tmp = bit1;
bit1 = bit2;
bit2 = tmp;
tmp = num1;
num1 = num2;
num2 = tmp;
}
int sub = bit1 - bit2;
int new_num2 = num2 * pow(10, sub) + num1 / pow(10, bit2 + 1);
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// this part is very important, it is very easy to be wrong! switch the position of num1 and num2 when comparing
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// this part is very important, it is very easy to be wrong! switch the position of num1 and num2 when comparing
if (num1 == new_num2) {
int base = pow(10, bit2 + 1);
num1 = num1 % base;
new_num2 = num1;
num1 = num2;
}
if (num1 > new_num2) {
if (swi) {
return false;
} else {
return true;
}
} else {
if (swi) {
return true;
} else {
return false;
}
}
}
}
//int num_rvt(int num){
// int result = 0;
// while (num > 0){
// result = result * 10 + num % 10;
// num /= 10;
// }
// return result;
//}
};
------------------------------------- codes ----------------------------------------
bool myfunction(string a, string b) {
int alen = a.size();
int blen = b.size();
int aind = 0;
int bind = 0;
while (aind < alen || bind < blen) {
if (a[aind % alen] < b[bind % blen]) {
return false;
} else if (a[aind % alen] > b[bind % blen]) {
return true;
} else {
aind++;
bind++;
}
}
return false;
}
class Solution {
public:
/**
*@param num: A list of non negative integers
*@return: A string
*/
string largestNumber(vector<int> &num) {
// write your code here
vector<string> str_num;
for (vector<int>::iterator it = num.begin(); it != num.end(); ++it) {
str_num.push_back(cvt(*it));
}
sort(str_num.begin(), str_num.end(), myfunction);
if (str_num[0].compare("0") == 0) return "0";
string result;
for (vector<string>::iterator it = str_num.begin(); it != str_num.end(); ++it) {
result += *it;
}
return result;
}
string cvt(int num) {
if (num == 0) {
return string("0");
}
string result;
while (num > 0) {
result = string(1, num%10 + '0') + result;
num = num / 10;
}
return result;
}
};
------------------------------------- codes ----------------------------------------
bool myfunction(string a, string b) {
int alen = a.size();
int blen = b.size();
int aind = 0;
int bind = 0;
while (aind < alen || bind < blen) {
if (a[aind % alen] < b[bind % blen]) {
return false;
} else if (a[aind % alen] > b[bind % blen]) {
return true;
} else {
aind++;
bind++;
}
}
return false;
}
class Solution {
public:
/**
*@param num: A list of non negative integers
*@return: A string
*/
string largestNumber(vector<int> &num) {
// write your code here
vector<string> str_num;
for (vector<int>::iterator it = num.begin(); it != num.end(); ++it) {
str_num.push_back(cvt(*it));
}
sort(str_num.begin(), str_num.end(), myfunction);
if (str_num[0].compare("0") == 0) return "0";
string result;
for (vector<string>::iterator it = str_num.begin(); it != str_num.end(); ++it) {
result += *it;
}
return result;
}
string cvt(int num) {
if (num == 0) {
return string("0");
}
string result;
while (num > 0) {
result = string(1, num%10 + '0') + result;
num = num / 10;
}
return result;
}
};
No comments:
Post a Comment