179. Largest Number

Medium

Description

給定一組非負整數 nums，將它們排列成最大的數字並回傳字串。結果可能很大，回傳字串而非數字。

Example:

Input: nums = [10, 2] Output: “210”

Intuition#

核心思路：自定義排序——比較兩個數 a 和 b 時，比較 "ab" 和 "ba" 的字串大小，較大的排前面。

不能單純比較數字大小（例如 3 > 30，但 “330” > “303”）
也不能單純比較字串字典序（例如 “9” > “34”，但需要 “934” > “349”）
正確做法：比較拼接結果 a+b vs b+a

Approaches#

1: Custom Comparator Sort#

概念: 將數字轉字串，用自定義比較器排序，最後拼接
時間複雜度: O(n log n * k) - 排序 O(n log n)，每次比較涉及字串拼接 O(k)，k 為平均數字位數
空間複雜度: O(n * k) - 字串陣列

class Solution {
    fun largestNumber(nums: IntArray): String {
        val strs = nums.map { it.toString() }
            .sortedWith { a, b -> (b + a).compareTo(a + b) }

        if (strs[0] == "0") return "0"  // 全是 0 的情況

        return strs.joinToString("")
    }
}

⭐2: Custom Comparator (Array Sort, 原地)#

概念: 同上邏輯但用陣列排序避免額外集合開銷，並用 StringBuilder 拼接
時間複雜度: O(n log n * k) - 排序主導
空間複雜度: O(n * k) - 字串陣列

class Solution {
    fun largestNumber(nums: IntArray): String {
        val strs = Array(nums.size) { nums[it].toString() }

        strs.sortWith(Comparator { a, b ->
            (b + a).compareTo(a + b)
        })

        if (strs[0] == "0") return "0"

        val sb = StringBuilder()
        for (s in strs) sb.append(s)
        return sb.toString()
    }
}

邊界情況：當所有數字都是 0 時（如 [0, 0]），排序後第一個元素是 “0”，結果應該回傳 “0” 而不是 “00”。

🔑 Takeaways#

Pattern: 自定義排列順序問題 -> 自定義 Comparator
關鍵技巧: 比較 a+b vs b+a 的拼接結果是經典手法，可以證明這個比較函數滿足傳遞性，因此排序結果是全局最優