力扣 179.最大数

原题链接

题解

首先，第一感觉是直接按照字符串本身大小排序再相连；但是通过样例二可知此方法错误。

因此，我们重新思考，上面的排序方法错误的原因在于上述的排序满足 s1<=s2，但是不满足s1+s2<=s2+s1（我们称之为加法的传递原则）。此时我们重新定义排序规则：当s1+s2<=s2+s1时就排序，否则保持。

code

class Solution {
public:
    static bool cmp(string a,string b){
        string one=a+b;
        string two=b+a;
        if (one<=two) return false;
        return true;
    }
    string largestNumber(vector<int>& nums) {
        int cnt=nums.size();
        string s="";
        string ss[105];
        for (int i=0;i<cnt;i++){
            ss[i]=to_string(nums[i]);
        }
        sort(ss,ss+cnt,cmp);

        
        for (int i=0;i<cnt;i++){
            if (s=="" && i<cnt-1 && ss[i]=="0") continue; 
            s+=ss[i];
        }
        return s;
    }
};