(Leetcode 2021 刷题计划) 179. 最大数

每日一题时间: 2020-04-12 题目链接: 179. 最大数 官方题解链接: 最大数

题目

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

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

代码语言：txt复制

示例 1：
输入：nums = [10,2]
输出："210"
示例 2：
输入：nums = [3,30,34,5,9]
输出："9534330"
示例 3：
输入：nums = [1]
输出："1"
示例 4：
输入：nums = [10]
输出："10"

提示：

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

解题方法

排序

解题思路: 如何确定两个数值应当哪个在前面?

1. 最高位影响其先后顺序
   • a = 300 和 b = 4 应当 b = 4 在前面
   • 此时博主构建 aStr 与 bStr 在补零情况下的排序 300 和 400 但是却遇到问题, 在于 30 和 3, 应当 3 优先
2. 优化单数对比逻辑改为组合对比逻辑
   • 哪个数优先, 在于其与其他数的组合情况下, 哪个数在前方更大, 采用组合逻辑可以简单比较 330 和 303 的大小

代码语言：txt复制

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        string res;
        sort(nums.begin(), nums.end(), [](int a, int b){
            return (to_string(a)   to_string(b)) > (to_string(b)   to_string(a));
        });
        if (nums[0] == 0) return "0";
        for (auto n: nums) {
            res  = to_string(n);
        }
        return res;
    }
};

• 复杂度分析
  • 时间复杂度: O(N log N)
  • 空间复杂度: O(log N)

参考资料

1. 179. 最大数
2. 最大数

leetcode

0 人点赞