原题目
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.
中文大意
给定多个非负整数，将他们重新编排，使得他们组成最大的数字，如[3, 30, 34, 5, 9]，重排后为[9,5,34,3,30]
题解
class Solution {PRivate: static bool cmp(string a,string b) { //针对题目要求对两个字符串进行特定的排序 return a+b > b+a; }public: string int2str(int a) //将一个数字转换为对应的字符串(很遗憾这里没有办法用itoa) { string ans; int base = 10; do { ans = char(a%base+'0') + ans; //取出单个数字加到字符串的最前面 a/=base; }while(a>0); return ans; } string largestNumber(vector<int>& nums) { string ans; vector<string> strs; // bool allZero = true; for(int i = 0; i < nums.size(); i ++) { strs.push_back(int2str(nums[i])); // if(nums[i]!=0) allZero = false; } // if(allZero) // { // ans = "0"; // return ans; // } sort(strs.begin(),strs.end(),cmp); for(int i = 0; i < strs.size() ;i++) { ans += strs[i]; } //直接将形如"0000"这样的结果变成0 if(ans[0]=='0' && ans.size()>1) ans = "0"; return ans; }};思路
这道题可以转换为，将给定的数字，按照从大到小的某种顺序，进行排序，然后将排序后的数组组合成字符串然而这里的顺序，并不能简单地按照数字大小来进行，例如： 3’>’30(330>303)34’>’3(343>334) 也就是说，对于两个数a,b,我们需要比较[ab]与[ba]的大小，如果[ab]>[ba]，那a就排在b的前面，反之b在a前面，这种顺序有点类似于字典序，在这里，我们姑且定义为“类字典序”原题目提到，最终组合出来的数，有可能会出现溢出的可能，所以需要以字符的形式输出结果，这也给了我们一定的提示：对于输入的每一个数字，最好是先转换为字符串，然后对字符串数组进行排序总的来说，本题的解决思路为：将读入的int数组（向量）转换为字符串数组（向量），然后对字符串向量进行以“类字典序”为顺序的排序，最后将排序后的字符串数组（向量）组合成一个字符串，作为结果最后的最后，还需要排除形如”0000”这样的情况。这里有两种解决思路：
在将整形转换为字符串的过程中，判断整个数组是否全是0，如果是，直接输出结果”0”，不进行后续的处理排序，组合得到结果之后，判断首字符是否为’0’，如果是，并且字符串的长度大于1，由于这样的结果是经过排序的，如果长度大于1，后面的字符必然为’0’，即得到形如”000”,”00000”这样的结果，这个时候直接输出”0”在上述的解答中，使用的是思路2，但同时也实现了思路1（注释代码部分）
本题中用到了排序，主要的计算量也在排序中，因此整体的算法的时间复杂度为O(nlogn)，空间复杂度为O(1)
