劍指offer：把數組排成最小的數

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

# -*- coding: utf-8 -*-
# @Time         : 2019-07-10 19:57
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : printMinNumber.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

class Solution:
    """
    要求對數組中的數字進行排序，使得排序后的數字最小。
    最樸素的做法就是遍歷所有可能的組合，然后選出最小的數字，但是這樣做的話要對n!個組合進行比較。

    換個思路，其實這道題就是要對數組中的元素進行一種排序，使得排序后的數組構成最小的數字。
    那么就是需要我們設計一種比較方式。
    假設數字m和數字n，有兩種組合方式mn和nm，注意到mn和nm的長度是一樣的，也就是當我們要比較mn和nm
    的大小的時候，可以直接比較這兩個數字的對應位數的數字。由于mn可能超出整型的表示范圍，因此我們需
    要將其轉換成字符串的比較，也是只需要比較兩個字符串的字典序即可。
    """
    def PrintMinNumber(self, numbers):
        def cmp_to_key(mycmp):
            # 由于在python3中已經移除了多輸入的比較函數，在查閱官方文檔后發現，排序函數中的比較
            # 函數返回的是一個對象，而不是一個比較的結果，在py3中可以用于選擇一個類或者一個多元素
            # 的對象中的一個作為排序的依據。
            # 因此我們定義一個類，在類中實現比較的函數，然后返回這個類。
            class K:
                def __init__(self, obj):
                    self.obj = obj

                # 一般來講要定義前五個比較函數，最后一個不等于感覺意義不大
                def __lt__(self, other):
                    # 需要注意的是這里的other參數也是K類型的，因此我們要將其obj屬性進行對比
                    return mycmp(self.obj, other.obj) < 0

                def __gt__(self, other):
                    return mycmp(self.obj, other.obj) > 0

                def __eq__(self, other):
                    return mycmp(self.obj, other.obj) == 0

                def __le__(self, other):
                    return mycmp(self.obj, other.obj) <= 0

                def __ge__(self, other):
                    return mycmp(self.obj, other.obj) >= 0

                def __ne__(self, other):
                    return mycmp(self.obj, other.obj) != 0

            return K

        # 實際上的比較函數是這個
        def cmp(num1, num2):
            if num1 + num2 > num2 + num1:
                return 1
            elif num1 + num2 == num2 + num1:
                return 0
            else:
                return -1

        if not numbers:
            return ""
        numbers = list(map(str, numbers))
        numbers.sort(key=cmp_to_key(cmp))
        return ''.join(numbers)

def main():
    solution = Solution()
    numbers = [3, 32, 321]
    print(solution.PrintMinNumber(numbers))

if __name__ == '__main__':
    main()