題目

179. Largest Number
難度: 中等

題意

給定一整數陣列nums，排序好nums使所有整數串接(concatenate)起來所代表的數最大；以字串回傳串接好的數。

範例1

Input: nums = [10,2]
Output: "210"

範例2

Input: nums = [3,30,34,5,9]
Output: "9534330"

方向

排序所有整數，排序比較一對整數時，比較他們分別串接誰比較大。
最後把所有整數轉成字串接在一起回傳。

實作1

排序時，對於要比較的一對整數a與b，先計算b有幾位數，a就乘上幾個0，再加上b。
比較ab與ba的值。

class Solution
{
private:
    int concate(int a, int b)
    {
        // Find number of digits in b
        int digits = (b == 0) ? 1 : log10(b) + 1;
        // Shift 'a' by 'digits' places and add 'b'
        return a * pow(10, digits) + b;
    }

public:
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [this](const int &a, const int &b){
            int ab = concate(a, b);
            int ba = concate(b, a);
            return ab > ba;
        });
        string res;
        for(auto num : nums)
            res += to_string(num);
        return res;
    }
};

這邊還出了個小插曲，若sort lambda function寫成:

sort(nums.begin(), nums.end(), [](const int &a, const int &b){
    int ab = concate(a, b);
    int ba = concate(b, a);
    return ab > ba;
});

則會出現錯誤:
error: ‘this’ was not captured for this lambda function
果然c++真菜，沒辦法一氣呵成......
要把this直接加入capture list裡。

結果1

翻車，顯然先乘再加會溢位，完全沒顧慮到QQ
Runtime Error 17/233 cases passed (N/A)
Error
Line 9: Char 16: runtime error: 1e+10 is outside the range of representable values of type 'int' (solution.cpp)
Line 9: Char 16: runtime error: 1e+10 is outside the range of representable values of type 'int' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior solution.cpp:9:16
Testcase
[999999991,9]
Expected Answer
"9999999991"

實作2

那我先轉成字串，再串接比較，就不會有溢位問題ㄌ吧?

class Solution
{
public:
    string largestNumber(vector<int>& nums) {
        vector<string> num_str;
        for(auto num : nums)
            num_str.push_back(to_string(num));
        sort(num_str.begin(), num_str.end(), [](const string &a, const string &b){
            return (a + b) > (b + a);
        });
        string res;
        for(auto str : num_str)
            res += str;
        return res;
    }
};

結果2

欸不是，leading zero要消除你要先說阿XD
確實是個容易出錯的細節...
Wrong Answer 229/233 cases passed (N/A)
Testcase
[0,0]
Answer
"00"
Expected Answer
"0"

實作3

確實地跳過所有非最後一位的零

class Solution
{
public:
    string largestNumber(vector<int>& nums)
    {
        vector<string> num_str;
        for (auto num : nums)
            num_str.push_back(to_string(num));
        sort(num_str.begin(),
             num_str.end(),
             [](const string& a, const string& b)
             { return (a + b) > (b + a); });
        string res;
        bool leading_zero = true;
        for (size_t i = 0; i < num_str.size(); i++)
        {
            string str = num_str[i];
            if (str != "0")
                leading_zero = false;
            if (!leading_zero || i == num_str.size() - 1)
                res += str;
        }
        return res;
    }
};

結果3

Accepted
233/233 cases passed (7 ms)
Your runtime beats 61.31 % of cpp submissions
Your memory usage beats 55.19 % of cpp submissions (17.2 MB)

分析

若nums數量為N
時間複雜度: O(NlogN)，排序所需
空間複雜度: O(N)，事先轉好字串所需

總結