题目链接：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.
这道题的要求是给一堆非负整数，然后将这些数字拼接成一个最大的数字，结果用字符串表示。
先想一下2个数字拼接的情形：如果两个数字数位相同，那么把大的放到前面就可以保证拼接后的数字最大了；如果两个数字数位不同，那么看似麻烦了啊，其实好办，假设两个数字分别为a和b，那么比较一下ab和ba那个大，就知道应该把那个数字放在前面了。
综上所述，就是要找出2个数字中“大”的，排在前面即可。而要想比较出“大”，可以比较一下哪个数字排在前面可以得到更大的结果，那么那个数字就是“大”的。
至于很多数字的情况，就是一个基于上面说明的“大”的排序的问题。
因此，需要先把数字数组转化成字符串数组，然后对其进行按照指定规则进行排序，然后再把排序后的每个字符串连接起来即可。其中排序函数如下：
static bool cmp(string a, string b)
{
return a + b > b + a;
}
时间复杂度：O(lnlogn)（l为数字平均位数）
空间复杂度：O(lnlogn)（l为数字平均位数）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
public:
string largestNumber(vector<int>& nums)
{
vector<string> vs(nums.size());
for(int i = 0; i < nums.size(); ++ i)
vs[i] = change(nums[i]);
sort(vs.begin(), vs.end(), cmp);
string res = "";
for(int i = 0; i < vs.size(); ++ i)
res += vs[i];
return res[0] == '0' ? "0" : res;
}
private:
string change(int n)
{
string s(1, (char)(n % 10 + '0'));
while(n /= 10)
s = (char)(n % 10 + '0') + s;
return s;
}
static bool cmp(string a, string b)
{
return a + b > b + a;
}
};