Given a list of non negative integers, arrange them such that they form the largest number.
Example 1:
Input:[10,2]Output: "210"
Example 2:
Input:[3,30,34,5,9]Output: "9534330"
Note: The result may be very large, so you need to return a string instead of an integer.
给定一个数组，要把数组中所有的数拼成一个长的数，问能够拼成的最大的数是多少，要求返回这个最大数的字符串形式。
要想长数越大，则数组中“越大的数”应该排在前面，这里的“大”是指字典序，比如9就比34大，所以9应该在字符串中排前面。所以大的思路是先把数字数组转换为对应的字符串数组，然后按字典序对字符串数组排序，最后按先后顺序拼接起来。
还有一个问题是，遇到30和34时，应该把34排在30的前面，即3430>3034，这符合字典序，没什么问题。
另一个问题是，遇到一个数是另一个数的前缀的情况，应该怎么排序呢，比如34和349时，应该是349排在34的前面，因为34934>34349，这也符合字典序。但是，如果是34和341，正确的排序应该是34排在341的前面，因为34341>34134，此时就不符合字典的降序了。所以需要自定义一个对字符串的排序算法，此算法要对字符串s1和s2进行比较，方法是判断s1+s2和s2+s1的字典序，因为这就是这两个字符串按不同顺序拼接之后的大小。
最后一个问题，如果遇到数组是[0,0]，即两个0时，能拼成的最大数是0，但是如果先转换成字符数组之后，拼成的数就是00了。所以在最后，我们判断一下开头的字符是否为’0’，如果是，说明这个数就是0了，不管后面是否还有多余的字符’0’，我们都只返回”0″。如果开头的字符不是’0’，则多个’0’是有效的，比如30和300是不同的两个数。
完整代码如下：
bool comp(const string& s1, const string& s2)
{
string tmp1 = s1 + s2, tmp2 = s2 + s1;
return tmp1 > tmp2;
}
class Solution {
public:
string largestNumber(vector<int>& nums)
{
vector<string> snums;
for (size_t i = 0; i < nums.size(); ++i)
snums.push_back(to_string(nums[i]));
sort(snums.begin(), snums.end(), comp);
string ans = "";
for (size_t i = 0; i < snums.size(); ++i)
ans += snums[i];
if (!ans.empty() && ans[0] == ‘0’)
return "0";
return ans;
}
};本代码提交AC，用时6MS。
代码中注意一点，自定义的比较函数不能是类的成员函数，要不然会报错“非标准语法；请使用 “&” 来创建指向成员的指针”，这个错误提示很奇怪。后来才知道比较函数必须定义成全局函数或者静态函数，因为sort自己就是全局或静态函数，无法调用成员函数。