0%

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

题目描述

题目链接: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 排序的依据不是两个数字本身大小,而是依据两个数字按前后顺序组合成的 abba 的大小来进行排序。(这一步可以通过转换为字符串进行操作),代码如下,其中要注意所有元素都是 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 为位数最多数字的长度)