題目描述:
給定一組非負整數 nums,將它們排列組合成最大的數字,以字串形式回傳。
解題思路:
核心思想是自定義排序。對於任意兩個數字 a 和 b,比較 ab(a 接 b)和 ba(b 接 a)哪個更大:
ab > ba,則 a 應排在 b 前面。a=9, b=34,比較 "934" vs "349",934 較大,所以 9 排前面。將所有數字轉為字串後,用此自定義比較器排序,最後串接所有字串即為最大數。
特殊情況:若排序後第一個元素是 "0",代表所有數字都是 0,直接回傳 "0"。
時間複雜度:O(n log n * k) — 排序為 O(n log n),每次比較兩個字串串接需要 O(k) 時間,其中 k 為數字的平均位數。
空間複雜度:O(n * k) — 儲存 n 個字串,排序需要 O(log n) 堆疊空間。
1. Convert each number in nums to a string -> strs[] 2. Sort strs with custom comparator: a+b > b+a means a comes first 3. If strs[0] == "0", return "0" (all zeros edge case) 4. Concatenate all strings in sorted order 5. Return the concatenated result
比較器的數學證明法:可以數學證明 a+b > b+a 定義了一個嚴格弱序(strict weak ordering),因此排序結果唯一且正確。也可用數學式替代字串比較:a * 10^len(b) + b > b * 10^len(a) + a,避免字串串接開銷。
基數排序法:對數字的每一位進行基數排序,需要特殊處理不同長度的數字(如 3 vs 30 vs 34)。實作複雜度高,且不如自定義比較排序直觀,面試中不推薦。