平武建站

剑指offer：把数组排成最小的数

题目描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

目前创新互联已为近1000家的企业提供了网站建设、域名、雅安服务器托管、网站托管、服务器托管、企业网站设计、祁门网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

# -*- 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()

当前文章：剑指offer：把数组排成最小的数
本文链接：http://pwwzsj.com/article/pdspes.html

其他资讯