题目如下：

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

分析如下：

先看几个例子

eg1. [0, 0, 0 , 0] ->  0

eg2. [1211, 12] -> 121211而不是121112。

所以可以考虑排序，而排序的根据(也就是比较函数的比较原理)不是这些数的值的相对大小，而是它们构成新的数的大小比较。

所以，虽然1211 > 12， 但是

"1211" + "12" = "121112", 

“12” + "1211" = "121211", 

"121112" < "121211" 

所以从构成新的数的角度来看, "1211" < "12" 。

我的代码：

//13ms
struct {bool operator()(string a, string b){string c1 = a + b;string c2 = b + a;return c1 > c2;}
} compareDigits;class Solution {
public:string largestNumber(vector<int> &num) {if (num.size() == 0) return "";vector<string> num_str;for (int i = 0; i < num.size(); ++i) {num_str.push_back(to_string(num[i]));}std::sort(num_str.begin(), num_str.end(), compareDigits);string res1 = "";for (int i = 0; i < num_str.size(); ++i)res1 += num_str[i];if (res1[0] == '0')return "0";elsereturn res1;}
};

小结扩展:

1 比较函数的写法，注意比较函数中的等号的处理。

一开始的错误写法如下，

struct {bool operator()(string a, string b){string c1 = a + b;string c2 = b + a;for (int j = 0; j < c1.length(); ++j) {if (c1[j] < c2[j])return false;else //错误,这里的else必须只能表示">"不能表示">=" 。因为这里的比较函数是对"<"写的。"="和">"都是false。return true;}return false;}
} compareDigits;

修改后为，

struct {bool operator()(string a, string b){string c1 = a + b;string c2 = b + a;for (int j = 0; j < c1.length(); ++j) {if (c1[j] < c2[j])return false;else if (c1[j] > c2[j])return true;}return false; //"="的case, 因为operator()表示小于，所以">" 或者 "="都为false;}
} compareDigits;

再简化一下，就是。

struct {bool operator()(string a, string b){string c1 = a + b;string c2 = b + a;return c1 > c2;}
} compareDigits;

2  另外一种思路。

上面的思路是O(NlgN)，下面看另外一种思路虽然是O(N²)， 但也不错，挑玉米算法。

class Solution {
public:string largestNumber(vector<int> &num) {string str = "";while(!num.empty()){int n = num.size();  int j = 0;int vv = num[j];for(int i=1;i!=n;i++){int uu = num[i];uu = num[i];vv = num[j];if(uu != vv)if(to_string(uu)+to_string(vv)>to_string(vv)+to_string(uu)){j=i; //j保持当前的"最大"string， "最大"在这里不是指它本身最大，而是指，如果它能够合成最大的数。}}str += to_string(num[j]);num.erase(num.begin()+j);}while(str[0]=='0'&&str.size()>1) str.erase(str.begin());return str;}
};