題目描述

輸入一個非負整數數組，把數組里所有數字拼接起來排成一個數，打印能拼接出的所有數字中最小的一個。

• 0 < nums.length <= 100
• 輸出結果可能非常大，所以你需要返回一個字符串而不是整數
• 拼接起來的數字可能會有前導 0，最后結果不需要去掉前導 0

題目樣例

示例

• 輸入: [10,2]

• 輸出: "102"

• 輸入: [3,30,34,5,9]

• 輸出: "3033459"

題目思考

1. 怎么定義最小?

解決方案

思路

• 分析題目, 要使得拼接起來的數字最小, 只有當各個拼接元素按照從小到大拼接起來才可以
• 而這里的從小到大拼接, 不是指按照數字本身順序或者字典序從小到大拼接
• 舉個例子, 90 和 902 的拼接結果應該是 90290, 但是 90 不管是數字還是字典序都小于 902
• 那如何定義哪個數字作為拼接后的第一個數字呢?
• 假如這個數字和任意其他數字拼接起來, 都小于將兩個數字互換后拼接的結果, 那么顯然這個數字就應該放在首位
• 到這里就知道了, 我們應該自定義一個排序方法, 對于兩個數字 a 和 b 而言, 比較              str(a)+str(b) 與              str(b)+str(a) 的大小關系, 然后對整個列表排序后組成一個字符串即可
• 下面的代碼使用兩種方案實現, 一種是快速排序, 一種是語言內置排序, 供大家參考

復雜度

• 時間復雜度              O(NlogN)
• 排序的時間復雜度
• 空間復雜度              O(N)
• 使用了額外的字符串數組

代碼

方案 1 - 自定義快速排序

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        # 使用map將原數組的數字轉成字符串
        nums = list(map(str, nums))

        def quicksort(l, r):
            # 經典快速排序實現
            if l >= r:
                return
            pivot = nums[l]
            i, j = l, r
            while i < j:
                # 只需要把這里改成自定義的排序方法即可
                while i < j and nums[j] + pivot >= pivot + nums[j]:
                    j -= 1
                nums[i] = nums[j]
                # 只需要把這里改成自定義的排序方法即可
                while i < j and nums[i] + pivot <= pivot + nums[i]:
                    i += 1
                nums[j] = nums[i]
            nums[i] = pivot
            quicksort(l, i - 1)
            quicksort(i + 1, r)

        quicksort(0, len(nums) - 1)
        return ''.join(nums)

方案 2 - 自定義內置排序

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        class compare(str):
            def __lt__(self, x):
                return self + x < x + self

        # 使用python內置sorted的key, 傳入一個重載__lt__的類, 自定義排序
        return ''.join(sorted(map(str, nums), key=compare))