题目描述
题目链接: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 即可:
#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 为位数最多数字的长度)