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;

    }

};

巴特西

179. 最大数 (Medium)

问题描述

解题思路

代码

最新文章

热门文章