179. Largest Number

problem description

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

Input: [10,2]
Output: "210"

Example 2:

Input: [3,30,34,5,9]
Output: "9534330"

Note: The result may be very large, so you need to return a string instead of an integer.

algorithm thought

其实这题本质上，就是将给定的数组，排个序。原始的排序算法，是将数字按照顺序排列，但是我们这里显然需要自己定义自己的顺序。这个顺序也很好定义，就是a+b>b+a。可以仔细理解一下，比较函数这么写的意义。

code

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> tmp;
        for(int num:nums)
            tmp.push_back(to_string(num));
        sort(tmp.begin(),tmp.end(),[](string s1,string s2){return s1+s2>s2+s1;});
        string res;
        for(string str:tmp)
            res+=str;
        while(res[0]=='0'&&res.size()>1){
            res.erase(0,1);
        }
        return res;
    }
};

algorithm analysis

字符串比较中如果两个字符串大小差不多可能需要时间复杂度为O(n),如果字符串平均长度为m，数组平均长度为n，那么时间复杂度为O(nlgn*m)