179 - Largest Number

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.

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

Hide Tags

Sort

先把数字都转成字符串，

然后做个特殊的排序，使得按照需要的大小排列，

最后把字符串串起来就好了。

但是写排序函数的时候，一开始思路有问题，陷入到很具体的数字比较了，

例如 (12, 121) (824, 8247) (2, 2281) ….

各种比较条件堆起来，排序函数写得巨复杂，越看越不对，铁定是思路错了。

后来想到，目的就是要组合出来的数字更大嘛，

那就把比较的两个字符串正串反串比一下不就好了么！

果然，一行就搞定了。。。

 

bool cmpstr (string a,string b)
{
    return (a+b)<(b+a); //这一贱的风情。。。
}

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> buf;
        string rst="";

        for(int ii=nums.size()-1; ii>=0; ii--)
            buf.push_back(to_string(nums[ii]));

        sort(buf.begin(), buf.end(), cmpstr);

        if('0' == (buf[buf.size()-1])[0])
            return "0";
           
        for(int ii=buf.size()-1; ii>=0; ii--)
            rst += buf[ii];
       
        return rst;
    }
};

8 ms.

 

如果是C，就没有sort函数可以用了，

但是。。。还有别的：用qsort的解法，原帖在此。