179. 最大数 (Medium)

问题描述

179. 最大数 (Medium)

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

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

示例 1：

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

示例 2：

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

提示：

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

解题思路

贪心，将数组转化为字符串数组，然后如果s1 + s2 >= s2 + s1，那么就保证s1一定在s2的前面，利用该规则自定义排序，同时要注意对数组中元素全为0的特殊条件的判断。

代码

class Solution {
  public:
    string largestNumber(vector<int> &nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                sum += nums[i];
                break;
            }
        }
        // 对数组元素全为0的特殊情况的判断
        if (sum == 0) {
            return "0";
        }
        vector<string> tmp;
        for (int &num : nums) {
            tmp.push_back(std::to_string(num));
        }
        // 自定义排序，确保如果s1 + s2 > s2 + s1，那么s1一定在s2前面
        auto cmp = [&](string &s1, string &s2) { 
            return s2 + s1 <= s1 + s2;
        };
        std::sort(tmp.begin(), tmp.end(), cmp);
        string res;
        for (auto &s : tmp) {
            res += s;
        }
        return res;
    }
};