2.7　最大數(shù)

題目描述（第179題）

給定一組非負(fù)整數(shù)，重新排列它們的順序使之組成一個最大的整數(shù)。

示例1

輸入：[10,2]

輸出：210

示例2

輸入：[3,30,34,5,9]

輸出：9534330

說明：輸出結(jié)果可能非常大，所以你需要返回一個字符串而不是整數(shù)。

思路

這道題其實(shí)是排序題目的變種，是一道披著數(shù)學(xué)外衣的排序題。

首先我們要知道一個數(shù)學(xué)常識。

1．如果兩個數(shù)位數(shù)不同，那么位數(shù)大的數(shù)更大。

2．如果兩個數(shù)位數(shù)相同，比如兩個數(shù)123a456和123b456，如果a> b，那么123a456大于123b456，否則123a456小于或等于123b456。也就是說，兩個相同位數(shù)的數(shù)的大小關(guān)系取決于第一個不同的數(shù)字的大小。

這道題由于總的位數(shù)是確定的，就是數(shù)組全部位數(shù)之和，因此我們的入手點(diǎn)就是上面提到的第2點(diǎn)，即越高位的數(shù)字越大越好，但是這里需要考慮特殊情況，題目給出的測試用例就能夠很好地說明問題。示例2中按降序排序得到的數(shù)是9534303，然而交換3和30的位置可以得到正確答案9534330，因此，在排序的比較過程中，我們需要自定義排序的策略，即自己決定哪個元素排在前面。一種方式是將比較元素（即題目中的非負(fù)整數(shù)）轉(zhuǎn)化為字符串，然后用字符串的比較即可避免上述問題。比如上述例子中的3和30，按照拼接后的字符串比較'303'和'330'哪個大，從而決定誰排在前面就好了。

我們可以先將數(shù)字?jǐn)?shù)組轉(zhuǎn)化為字符串?dāng)?shù)組，然后排序，這個過程需要定制比較邏輯。和其他編程語言一樣，Python支持這種自定義的比較邏輯，如果你不熟悉也沒關(guān)系，這里簡單地講解一下，熟悉的讀者可以選擇跳過本部分內(nèi)容。

對于s.sort(reverse=True,key=functools.cmp_to_key(comp))而言，comp是我們自定義的比較函數(shù)，它接收兩個參數(shù)，分別是a和b，表示需要進(jìn)行比較的兩個元素。接下來是重點(diǎn)。

●　如果返回值為正，則b在前，a在后。

●　如果返回值為負(fù)，則a在前，b在后。

●　如果返回值為0，則保持相對位置不變。

你只需要自定義并實(shí)現(xiàn)比較邏輯，然后返回正數(shù)、負(fù)數(shù)或0即可。

代碼

如果你喜歡短小精悍的代碼，可以參考下面這段代碼。

復(fù)雜度分析

●　時間復(fù)雜度：這里總的時間復(fù)雜度是由排序決定的，因此這種算法的時間復(fù)雜度為O(nlogn)，其中n為數(shù)組長度。

●　空間復(fù)雜度：由于我們將輸入轉(zhuǎn)化成了字符串?dāng)?shù)組，因此這里的空間復(fù)雜度為O(n)，其中n為數(shù)組長度。

擴(kuò)展

如果改為求最小數(shù)該怎么做？我們的解題策略需要做怎樣的調(diào)整？