【4.12】LeetCode每日一题· 最大数

2021年04月12日 12时08分

标签： LeetCode 数学贪心

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

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

#### 示例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] <= 10^9
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/largest-number/ "题目链接")

## 解题思路
很经典的题目。贪心，比较数字`a`和`b`的两种字符串拼接：`a+b`和`b+a`的字典序大小即可。字典序越大，放在越前面。

注意⚠️：如果输入是若干个0的话，会导致前导0的出现，需要特判后删除所有的前导零！这一点很容易忘记导致出错！

Tips：直接定义比较函数，然后对`vector`排序的空间占用应该少一点。STL实现空间复杂度实在太高了。

## 代码
```cpp
class Number{
    private:
    int value;
    int length;
    public:
    string s;
    Number(int value){
        this->value = value;
        if(!value) s = "0";
        while(value){
            s.insert(s.begin(), value%10 + '0');
            value/=10;
        }
        length = s.length();
    }
    bool operator <(const Number& num)const{
        string s1 = this->s + num.s, s2 = num.s + this->s;
        return s1 < s2;
    }
};
class Solution {
public:
    string largestNumber(vector<int>& nums) {
        priority_queue<Number> que;
        for(int& num: nums){
            que.push(Number(num));
        }
        string res;
        while(!que.empty()){
            res += que.top().s; que.pop();
        }
        // 去除前导0
        while(res[0] == '0' && res.length() > 1){
            res.erase(res.begin());
        }
        return res;
    }
};
```

## 用时和内存
> 执行用时：8 ms，在所有 C++提交中击败了89.79%的用户
> 内存消耗：11.4 MB，在所有 C++提交中击败了12.40%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.12】LeetCode每日一题· 最大数

所有评论

暂无评论

新增评论