题解 | 最大数

题干分析

题目给定我们一个整数数组,要求我们返回一个按照一定顺序排列后,将数组所有元素按序拼接为一个整数,使这个整数最大,要求我们返回这个整数的字符串.

算法思路

由于我们知道针对字符串而言,我们一般使用字典序比较两个字符串的大小.我们首先将问题缩小,针对两个正整数如何排序能使其拼接后值最大,由于两个整数拼接后一定等长(位数相同),因此很明显的高位更大的整数值更大,而这正好是字符串字典序判断大小的依据,由此我们只需要将原数组全转换为字符串,然后使用自定义的排序比较器将数组排序后拼接即可.

实现代码

string largestNumber(vector<int>& nums) {
    const int n = static_cast<int>(nums.size());
    vector<string> s_nums(n);
    for (int i = 0; i < n; ++i) s_nums[i] = std::to_string(nums[i]);

    ranges::sort(s_nums, [&](const string &a, const string &b) -> bool {
        return a + b > b + a;
    });

    if (s_nums[0] == "0") return "0"; // 特判

    string ans;
    for (const auto &s: s_nums) ans += s;

    return ans;
}

复杂度分析

• 时间复杂度: 字符串拼接O(n),令数组整数最值为m,排序比较次数nlogn次,每次比较耗时O(logm),总计为O(nlog(nm))
• 空间复杂度: 额外字符串数组空间开销:O(nlogm),递归栈消耗O(logn),总计O(nlogm)