XTAO's Tech Blog
0%

[Leetcode]179. Largest Number(C++)

发表于 更新于 分类于 ， 评论数：
1.2k 1 分钟

题目描述

题目链接：179. Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

例子

例子 1

Input: [10,2]
Output: “210”

例子 2

Input: [3,30,34,5,9]
Output: “9534330”

Note

The result may be very large, so you need to return a string instead of an integer.

解题思路

这道题要求我们将数字按照特定顺序排列使得最后结果最大，可以考虑用排序算法来做。对于 a, b 排序的依据不是两个数字本身大小，而是依据两个数字按前后顺序组合成的 ab 和 ba 的大小来进行排序。（这一步可以通过转换为字符串进行操作），代码如下，其中要注意所有元素都是 0 的情况只需要返回 0 即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

class Solution {
public:
    std::string largestNumber(std::vector<int>& nums) {
        std::vector<std::string> nums_str;
        bool has_non_zero = false;
        for (int num: nums) {
            nums_str.push_back(std::to_string(num));
            if (num && !has_non_zero) has_non_zero = true;
        }
        if (!has_non_zero) return "0";

        std::sort(nums_str.begin(), nums_str.end(), [](const std::string& lhs, const std::string& rhs) {
            if (lhs == rhs) return true;
            return (lhs + rhs) > (rhs + lhs);
        });

        std::string result;
        for (int i = 0; i < nums_str.size(); i++) result += nums_str[i];

        return result;
    }
};
  • 时间复杂度: O(nlogn)（不考虑字符串长度），O(nlognk) （考虑字符串长度， k 为位数最多的数字长度）
  • 空间复杂度: O(n) （不考虑字符串长度）， O(nk) （考虑字符串长度， k 为位数最多数字的长度）

推荐文章