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.
思路：
忧伤的发现，人的思路真的是很容易定型。这道题我做过的，但是过了这么久，我还是只记得我自己的老思路。
直接上正确答案， 关键是排序时比较的策略， 用s1+s2 和 s2+s1 比较即可，就是把两种方式排列的情况都试一下，看哪个大！！
class Compare{
public:
bool operator()(string s1, string s2)
{
return s1 + s2 < s2 + s1;
}
};
class Solution {
public:
string largestNumber(vector<int> &num) {
int i;
for (i = ; i < num.size(); i++)
if (num[i] != )
break;
if (i == num.size()) // All numbers are 0
return "";
vector<string> v;
for (i = ; i < num.size(); i++)
v.push_back(to_string(num[i]));
sort(v.begin(), v.end(), Compare());
string result;
for (i = v.size() - ; i >= ; i--)
result += v[i];
return result;
}
};
我自己的思路：
两个数比较 如 724 和7247 那么比较 724|724 与 7247|7247 即相同时就不断复制自己，直到遇到不同的数字得到大小。 如果两个数字同时达到末尾，但是数字一直相同，则这两个数字相同。
代码很长，但是也AC了，慢一些。主要是二分归并排序是我自己写的。
class Solution {
public:
string largestNumber(vector<int> &num) {
MergeSort(num, , num.size() - );
string ans;
for(int i = ; i < num.size(); i++)
{
stringstream ss;
ss << num[i];
string s = ss.str();
ans.append(s);
}
if(!ans.empty() && ans[] == '')
{
ans = "";
}
return ans;
}
bool islarge(int aa, int bb)
{
stringstream ss;
ss << aa;
string sa = ss.str();
ss << bb;
string sb = ss.str();
int i = , j = ;
while(sa[i % sa.length()] == sb[j % sb.length()]
&& !((i + ) % sa.length() == && (j + ) % sb.length() == )) //两边同时结束时跳出，防止相同数字无限循环
{
i++; j++;
}
return sa[i % sa.length()] > sb[j % sb.length()];
}
void MergeSort(vector<int> &in, int l, int r)
{
if(l < r)
{
int mid = (l + r) / ;
MergeSort(in, l, mid);
MergeSort(in, mid + , r);
Merge(in, l, mid, r);
}
}
void Merge(vector<int> &in, int l, int mid, int r)
{
vector<int> left(in.begin() + l, in.begin() + mid + ), right(in.begin() + mid + , in.begin() + r + );
int i = , j = , k = ;
while(i < left.size() && j < right.size())
{
if(islarge(left[i], right[j]))
{
in[l + k] = left[i++];
}
else
{
in[l + k] = right[j++];
}
k++;
}
while(i < left.size())
{
in[l + k] = left[i++];
k++;
}
while(j < right.size())
{
in[l + k] = right[j++];
k++;
}
}
};