劍指offer：把數(shù)組排成最小的數(shù)

題目描述
輸入一個(gè)正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來(lái)排成一個(gè)數(shù)，打印能拼接出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{3，32，321}，則打印出這三個(gè)數(shù)字能排成的最小數(shù)字為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:
    """
    要求對(duì)數(shù)組中的數(shù)字進(jìn)行排序，使得排序后的數(shù)字最小。
    最樸素的做法就是遍歷所有可能的組合，然后選出最小的數(shù)字，但是這樣做的話要對(duì)n!個(gè)組合進(jìn)行比較。

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

                # 一般來(lái)講要定義前五個(gè)比較函數(shù)，最后一個(gè)不等于感覺(jué)意義不大
                def __lt__(self, other):
                    # 需要注意的是這里的other參數(shù)也是K類型的，因此我們要將其obj屬性進(jìn)行對(duì)比
                    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

        # 實(shí)際上的比較函數(shù)是這個(gè)
        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()