题目描述

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

样例

输入: [10,2]
输出: 210

输入: [3,30,34,5,9]
输出: 9534330

说明

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

算法

(贪心，排序) $O(n \log n)$

1. 考虑简单的情况，如果只给了两个数字，那么只需要比较两个数字前后的拼接，即可确定顺序。
2. 扩展到多个数字时，存在偏序关系，即当 A 一定要在 B 前且 B 一定要在 C 前时，A 一定在 C 前。
3. 所以可以借助这个偏序关系直接对所有数字按照两个数字的情况进行排序。
4. 注意最后需要去除前导 0。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$，构造答案的时间复杂度近似为 $O(n)$。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储答案。

C++ 代码

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [](int x, int y) {
            string sx = to_string(x);
            string sy = to_string(y);
            return sx + sy > sy + sx;
        });

        string ans;
        for (int i = 0; i < nums.size(); i++)
            ans += to_string(nums[i]);

        for (int i = 0; i < ans.length() - 1; i++)
            if (ans[i] != '0')
                return ans.substr(i, ans.length() - i);

        return ans.substr(ans.length() - 1);
    }
};