【牛客题霸题解】最大数

排列给出的数据组成一个最大的数。就是一个顺序的问题。
先说一个可能会很容易想到的错误方案：
大的数数字在前面，小的数字在后面
举一个反例说明一下这个方案为什么错：{9,10} 排出来的最大数字是910，但是这样排的结果是109
那我们就来考虑一下，到底按一个什么样的方式排序才是正确的。
对于两个数字A、B来说，如果AB>BA,那么A就应该放在B的前面。（AB表示数字A和B进行拼接）
（这个前面不一定是紧挨着B，还有可能是EACDBF这样）
比如 我现在有一些数字是这样排列的;
ECDBAF
然后
AB>BA ，那么ECDABF>ECDBAF
交换了AB的顺序以后，如果AD>DA,那么A的顺序还要前移。
所以，这个规则就是我们排成最大数的正确规则了。写代码的时候只需要写一下排序规则，然后调用sort函数就可以了。
排序的时候数字已经转化为字符串了，AB和BA这两个字符串的长度是相等的，所以判断数值大小可以直接按字典序比较。
注意有一种特殊的情况{0,0,0,0,0}这样最大数应该是0，而不是00000。需要特判一下

c++

#include<algorithm>
bool cmp(string a,string b)
{
    return a+b>b+a;
}
class Solution {
public:
    string solve(vector<int>& nums) {
        vector<string> S;
        for(int i = 0 ; i < nums.size() ; i++)
        {
            S.push_back(to_string(nums[i]));
        }
        sort(S.begin(),S.end(),cmp);
        if(S[0]=="0")
        {
            return "0";
        }
        string ans = "";
        for(int i = 0 ;i < S.size() ; i++)
        {
            ans+=S[i];
        }
        return ans;
    }
};

java

import java.util.*;


public class Solution {
    public String solve (int[] nums) {
        String[] S = new String[nums.length];
        for(int i = 0 ; i < nums.length ; i++)
        { 
            S[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(S, new Comparator<String>(){
            @Override
            public int compare(String a,String b){
                return (b+a).compareTo(a+b);
            }
        });
        if(S[0].equals("0"))
        {
            return "0";
        }
        String ans = "";
        for(int i = 0 ;i < S.length ; i++)
        {
            ans+=S[i];
        }
        return ans;
    }
};

python

class Cmp(str):
    def __lt__(a, b):
        return a+b>b+a;

class Solution:
    def solve(self , nums ):
        S = [str(i) for i in nums]
        S = sorted(S,key = Cmp)
        if S[0] == "0":
            return "0"
        else:
            return "".join(S)