LeetCode 179：最大數——自定義排序規則

題目描述

給定非負整數數組，重新排列順序使拼接成的數字最大。結果可能很大，返回字符串。

示例

輸入：[3, 30, 34, 5, 9]
輸出："9534330"

核心洞察：自定義比較器

對於兩個數字字符串 a、b，比較 a+b 與 b+a 的字典序：

• a+b > b+a → a 排在 b 前面
• 例如 "3" vs "30"："330" > "303" ⇒ 3 在前

C++ 實現

class Solution {
public:
    static bool cmp(const string& a, const string& b) {
        return a + b > b + a;
    }
    string largestNumber(vector<int>& nums) {
        vector<string> strs;
        for (int n : nums) strs.push_back(to_string(n));
        sort(strs.begin(), strs.end(), cmp);
        if (strs[0] == "0") return "0"; // 全零情況
        string res;
        for (auto& s : strs) res += s;
        return res;
    }
};

關鍵細節

• 轉字符串比較避免大數溢出
• 全零輸入需特判返回 "0" 而非 "000..."
• 比較器必須滿足嚴格弱序（本題 a+b > b+a 可傳遞）

複雜度

• 時間：O(n log n · k) —— k 為平均數字長度
• 空間：O(n · k) —— 字符串存儲