前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >(Leetcode 2021 刷题计划) 179. 最大数

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

原创
作者头像
windism
修改2021-04-12 17:45:42
4720
修改2021-04-12 17:45:42
举报
文章被收录于专栏:风扬

每日一题时间: 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 = 300b = 4 应当 b = 4 在前面
    • 此时博主构建 aStrbStr 在补零情况下的排序 300400 但是却遇到问题, 在于 303, 应当 3 优先
  2. 优化单数对比逻辑改为组合对比逻辑
    • 哪个数优先, 在于其与其他数的组合情况下, 哪个数在前方更大, 采用组合逻辑可以简单比较 330303 的大小
代码语言: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. 最大数

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 解题方法
    • 排序
    • 参考资料
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档