179. 最大數（點擊查看題目）
題目描述
給定一組非負整數，重新排列它們的順序使之組成一個最大的整數。
示例 1:
示例 2:
說明: 輸出結果可能非常大，所以你需要返回一個字符串而不是整數。
解決方案
自定義排序：
想法
為了構建最大數字，我們希望越高位的數字越大越好。
算法
首先，我們將每個整數變成字符串。然後進行排序。
如果僅按降序排序，有相同的開頭數字的時候會出現問題。比方說，樣例 2 按降序排序得到的數字是 95343303，然而交換 3 和 30 的位置可以得到正確答案 9534330。因此，每一對數在排序的比較過程中，我們比較兩種連接順序哪一種更好。我們可以證明這樣的做法是正確的：
假設（不是一般性），某一對整數 a 和 b，我們的比較結果是 a 應該在 b 前面，這意味著 a ⌢ b > b ⌢ a，其中 ⌢ 表示連接。如果排序結果是錯的，說明存在一個 c，b 在 c 前面且 c 在 a 的前面。這產生了矛盾，因為 a ⌢ b > b ⌢ a 和 b ⌢ c > c ⌢ b 意味著 a ⌢ c > c ⌢ a。換言之，我們的自定義比較方法保證了傳遞性，所以這樣子排序是對的。
一旦數組排好了序，最“重要”的數字會在最前面。有一個需要注意的情況是如果數組只包含 0，我們直接返回結果 0 即可。否則，我們用排好序的數組形成一個字符串並返回。
Java 實現
Python 實現
複雜度分析
- 時間複雜度：O(nlgn)
儘管我們在比較函數中做了一些額外的工作，但是這只是一個常數因子。所以總的時間複雜度是由排序決定的，在 Python 和 Java 中都是 O(nlgn)。
- 空間複雜度：O(n)
這裡，我們使用了 O(n) 的額外空間去保存 nums 的副本。儘管我們就地進行了一些額外的工作，但最後返回的數組需要 O(n) 的空間。因此，需要的額外空間與 nums 大小成線性關係。
閱讀更多 力扣LeetCode 的文章
