返回

[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 即可:

#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 为位数最多数字的长度)
Built with Hugo
Theme Stack designed by Jimmy