原题地址：

 

题目内容：

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.

 

方法：

非常简单。

0. 定义两个整数的大小方式：有整数A和B，若AB > BA，则A > B

1. 调用sort，传入重新定义的比较函数，按递减排序。

2. 从0开始，将每个整数转为字符串，并push到结果字符串的末尾。结果字符串当然要初始化为0.

 

这里稍微提一下两个整数的大小比较方式。A = 9，B = 12这种情况就不说了，假设A的长度小于B，而且若A和B的前半部分完全一致，A和B的大小怎么处理？例如A = 12, B = 128的情况，还有A = 9，B = 912的情况。

不妨设B和A不相等的部分为C，则第一种情况C = 8，第二种情况C = 12。那么实际上B = AC，AB = AAC， BA = ACA。容易看出，AB和BA的头肯定是A，关键是AC大还是CA大。若AC大，则A大于B，若CA大，则B大于A。

当然你也可以简单粗暴直接把AB和BA连接起来，从字符串的角度看看谁大。这个我没有试过，不知道会不会TLE。可惜由于溢出问题，所以不能用整数表示，只能用字符串。

 

经验教训：

开始老是出RE，结果问题居然是sort函数：传入的compare方法不能同时对A < B和B < A返回真，也就是说，不能写类似 return A <= B的语句，否则sort会读一些乱七八糟的内存区域，然后就挂了

 

全部代码：

class Solution {public:    // define x < y. when x < y return true.    static bool compare(int x,int y) {        string a = strval(x);        string b = strval(y);        int length = a.size() > b.size() ? b.size() : a.size();        for (int i = 0; i < length; i ++) {            if (a[i] != b[i]) {                return a[i] - b[i] > 0;            }        }        return a.size() < b.size() ?                     (b.compare(b.substr(a.size()) + b.substr(0,a.size())) > 0 ? true : false)                    :                     (a.compare(a.substr(b.size()) + a.substr(0,b.size())) < 0 ? true : false);    }    string largestNumber(vector
     
       &num) {        sort(num.begin(),num.end(),compare);        if (num[0] == 0) {            return "0";        }        string result = "";        for (int i = 0; i < num.size(); i ++) {            result += strval(num[i]);        }        return result;    }        static string strval(int num) {        char tmp[20];        char index = 0;        while (num >= 10) {            tmp[index ++] = (char)(num % 10 + '0');            num /= 10;        }        tmp[index] = (char)(num + '0');        string res = "";        for (int i = index; i >= 0; i --) {            res = res + tmp[i];        }        return res;    }};