Leetcode每日一题 179. 最大数

¶179. 最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10,2]
输出："210"  

示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"

示例 3：

输入：nums = [1]
输出："1"

示例 4：

输入：nums = [10]
输出："10"

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 109

---

刚看到这题的想法是，找数字的优先级，然后从小往大排，比如34，3谁应该排在后面，一开始认为是从数字的个位开始遍历，34的个位为4，3的个位为3，那么3应该排在34的后面，形成了343，甚至满足前面4个示例，比如示例2，[3,30,34,5,9] 按个位比较后得到[30,3,34,5,9]，那么从小到大排我们得到
“9<-5<-34<-3<-30”，与答案符合，但是最后发现这并不是所有的最佳解，还是会有特殊情况，并不满足这个排序条件。

正确解法应该是先合并，后考虑谁大，最后再排序。
将nums数字里面的类容转化成字符串然后放进变量类型为string的str数组里。
使用sort的快排加上自定义函数，利用string的特性去让它自己判断大小，比如34和3，会直接比较343和334，343比较大，然后来排序。

最后是考虑，假如数组里全是0的话，那么我会得到"000…“,所以判断，假如数组第一位是0的话，意味着后面都是0，那么我们直接返回"0”。

class Solution {
public:
    static bool cmp(const string& a, const string& b)
    {
        return a+b > b+a;
    }
public:
    string largestNumber(vector<int>& nums) {
        vector<string> str;

        for(int x : nums)
        {
            str.push_back(to_string(x));
        }
        sort(str.begin(),str.end(),cmp);

        string res ="";
        for(auto x : str)
        {
            res+=x;  
        }

        return res[0] == '0'? "0" : res;
    }
};