剑指offer_45_把数组排成最小的数

把数组排成最小的数

题目链接：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/

题目内容：

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"

示例 2:

输入: [3,30,34,5,9]
输出: "3033459"

提示:

0 < nums.length <= 100

说明:

输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

题目解析

题目解析内容来自于题解中Krahets 和 bigkjp97

分析

题目的意思首先要明确，不是说把列表中每个数拆分开，而是，将数组合起来，组成一个最小的数。

这就转换成了让这个列表按照组合后数字最小的模式排序。也就是说，要定一个规则，使得列表中的数字按照这个规则从小到大排序。

现在我们就来找这个排序规则：

这里放一个示例，供大家理解。

test_list = [3, 30, 34, 5, 9]  # 示例列表

由题意，当 '30' + '3' = '303', '3' + '30' = '330' 时，'303' < '330', 则可知 '30' + '3' < '3' + '30', 也即 30 应该在数组按照规则排序后应排在 3 前面。

同理， '30' + '34' = '3034', '34' + '30' = '3430', '3034' < '3430', 则 '30' + '34' < '34' + '30', 即 30 在 34 前面。

照此逻辑，可以类推。

则可以得出这个排序规则：x + y < y + x ===> x < y

根据这个规则，使用任何一种排序方法都可以对指定列表进行排序，从而得到最小的排列结果。

算法流程：

初始化：根据数字列表生成字符串列表
字符串列表排序：根据上面发现的规则进行字符串列表的排序
返回：拼接字符串列表为字符串，并返回

复杂度分析：

时间复杂度 O(NlogN): N 为最终返回值的字符数量(字符串列表的长度 <= N); 使用快排或者内置函数的平均时间复杂度为O(NlogN), 最差为 O(N²)
空间复杂度 O(N): 字符串列表占用线性大小的额外空间

代码

快排方式

class Solution:
    def minNumber(self, nums):
        def fast_sort(strs):
            if len(strs) <= 1:
                return strs
            less, greater = [], []
            p = strs.pop()
            for i in strs:
                if i + p < p + i:
                    less.append(i)
                else:
                    greater.append(i)
            print(less, greater, p, type(p))
            
            return fast_sort(less) + [p] + fast_sort(greater)
        
        strs = [str(num) for num in nums]
        res = fast_sort(strs)
        return ''.join(res)

内置函数方式

class cmpSmaller(str):
    def __lt__(self, y):
        return self + y < y + self  # 字符串拼接比较(两两比较)
    # 按由小到大来排列

class Solution:
    def minNumber(self, nums):
        res=sorted(map(str, nums),key=cmpSmaller)
        smallest = ''.join(res)
        return smallest

sort 是只可比较 list 类型；sorted 可比较所有可迭代对象

附加说明

快排方式，无需多言。内置函数，实可深究。

内置函数方式自定义了一个类 comSmaller 继承了 str 类。并且重写了其 __lt__方法。这个方法就是当程序使用 < 比较时，程序内部调用的方法。具体解析可点此了解

现在我们来看一下这个 sorted 是怎么运行的。点此了解

官方文档是这么说的：
key 形参的值应该是一个函数，它接受一个参数并并返回一个用于排序的键。这种技巧速度很快，因为对于每个输入记录只会调用一次 key 函数。

也就是说，当我们指定 key 为 cmpSmaller 时，即 key 此时就是类 cmpSmaller 的别名。此时，在 sorted 内部，每一个待排序的字符串，被 key(strs中的字符串) 给重写了 __lt__ 方法。

key 返回用于排序的键，也即是这个重写了 __lt__ 的字符串, 此时，sorted 对其待排序内容时，调用 < 或 > 时，会自动调用这个重写的 __lt__ 方法。
即使用了我们上面分析时自定义的字符串比较规则。从而可以得到按照自定义指定规则从小到大排序好的字符串列表。