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 100 100
0 <= nums[i] <= 1 0 9 10^{9} 109

代码与思路

大概思路就是比较两个数，依次比较他们的最高位，如果最高位相同，比较次高位。（两个数位数不一样可以比较吗，也是可以的，比如[45,123]，4大于1，所以45放前面），这种排序对于输入数组没有相同数字开头的时候是有效的，比如{ 45,56,81,76,123 };得81765645123。
输入数组有相同数字开头的情况：
[4,42]比较，442>424，所以要把4放在前面;
[4,45]比较，454>445，所以要把45放在前面。
两个数字比较后，相对位置的关系就知道了，没有必要进行全排列比较。

#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <numeric>
using namespace std;
class Solution { 
public:
    string largestNumber(vector<int>& nums) { 
        vector<string> vs;
        transform(nums.begin(), nums.end(), back_inserter(vs), [](int x) { return to_string(x); });// algorithm---transform
        sort(vs.begin(), vs.end(), [](const string& a, const string& b) { 
            return a + b > b + a;
            });
        string res = accumulate(vs.begin(), vs.end(), string());// numeric---accumulate
        return res[0] == '0' ? "0" : res;
    }
    string largestNumber2(vector<int>& nums) { 
        // 将 nums 中的元素按照如下示例规则排序：
        // 因 "2" + "10" > "10" + "2" , 故 2 排在 10 的前面 
        sort(nums.begin(), nums.end(), [](int x, int y) { 
            string a = to_string(x), b = to_string(y);
            return a + b > b + a;
        });
        // 将排序后的数组转为字符串
        string ans = "";
        for (int n : nums) ans += to_string(n);
        // 输入为 [0,0] 时，输出应该为 "0"
        return ans[0] == '0' ? "0" : ans;
    }
};
int main()
{ 
    int nums[] = {  3,30,34,5,9 };
    vector<int> v(nums, nums + 5);
    for (auto it : v)
    { 
        cout << it << endl;
    }
    Solution s;
    cout << s.largestNumber(v) << endl;
}