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]，需要自己定义一种降序排列的比较方法。对于数组中的任何两个数a，b，如果ab>ba，，那么表示a>b。 这样将这种比较算法传递给sort函数，就可以对数组进行降序排列。再将这个整型数组转换成字符串即可。 还需要考虑的一种特殊用例就是排序后的第一个数字为0，这种情况下数组中所有元素都为0，但是只需要返回一个0。 排序函数可以在字符串这一级进行比较，也可以在整数这一级进行比较。 解法一：字符串比较 runtime:28ms
class Solution {public:string largestNumber(vector<int>& nums) {if(nums.size()==0)return “”;string str;sort(nums.begin(),nums.end(),big);for(int i=0;i<nums.size();i++){str+=to_string(nums[i]);}if(nums[0]==0)return “0”;return str;}big(int a,int b){string strA=to_string(a)+to_string(b);string strB=to_string(b)+to_string(a);return strA>strB;}};
上面有几个编程方面的问题，第一次处理花了不少时间。
解法二：在整数级进行比较 runtime:8ms
class Solution {public:string largestNumber(vector<int>& nums) {if(nums.size()==0)return “”;string str;sort(nums.begin(),nums.end(),compareGreater);for(int i=0;i<nums.size();i++){str+=to_string(nums[i]);}if(nums[0]==0)return “0”;return str;}numDigits(int num){unsigned int count = 0;do{count++;num /= 10;} while (num);return count;}compareGreater(int lhs, int rhs){unsigned int left_n = numDigits(lhs);unsigned int right_n = numDigits(rhs);unsigned int L = lhs*pow(10, right_n) + rhs;unsigned int R = rhs*pow(10, left_n) + lhs;return L > R;}};
自己打败自己的远远多于比别人打败的。
