179 最大数

本文最后更新于：2021年7月12日 下午

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

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

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：nums = [1]
输出："1"

示例 4：

1
2
输入：nums = [10]
输出："10"

提示：

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

Solution

参考：@宫水三叶

  • 字符串排序

  • 如果拼接结果 ab 要比 ba 好，那么我们会认为 a应该放在 b 前面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// @lc code=start
class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> str;
        for (int num : nums) str.push_back(to_string(num));
        auto cmp = [] (const string& str1, const string& str2) {
            return str1 + str2 > str2 + str1;
        };
        sort(str.begin(), str.end(), cmp);
        string res;
        for (string s : str) res += s;
        if (res[0] == '0') return "0";
        return res;
    }
};
// @lc code=end
algo leetcode 字符串 排序

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！