@ 劍指offer（python）把數組排成最小的數

劍指offer刷題筆記32（python）

題目描述

輸入一個正整數數組，把數組裡所有數字拼接起來排成一個數，列印能拼接出的所有數字中最小的一個。例如輸入數組{3，32，321}，則列印出這三個數字能排成的最小數字為321323。

思路

首先将數組中的元素轉化成字元串的形式，以便直接進行拼接。可以看到，輸出結果就是對原來的數組元素進行排序之後，再連接配接輸出。但是，這裡不能用傳統的單純比較大小的規則，這裡需要重新定義一個比較大小的規則：

若ab > ba 則 a > b，

若ab < ba 則 a < b，

若ab = ba 則 a = b；

是以，可以利用這個規則，對轉換成字元串的數組進行排序，并連接配接起來。

是以，我們可以在快排中修改排序規則，利用修改之後的快排對字元進行排序。

代碼

# -*- coding:utf-8 -*-
class Solution:  
    # 自定義排序規則加快排
    def PrintMinNumber(self, numbers):
        # write code here
        if numbers is None or len(numbers) == 0:
            return ""
        numbers = map(str, numbers)
        pivot = numbers[0]
        less = [i for i in numbers[1:] if (pivot+i)>(i+pivot)]
        great = [i for i in numbers[1:] if (pivot+i)<=(i+pivot)]
        result = "".join(self.PrintMinNumber(less))+pivot+"".join(self.PrintMinNumber(great))
        return result.lstrip("0")