剑指offer-45

剑指 Offer 45. 把数组排成最小的数

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

示例

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

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

官方题解

此题求拼接起来的最小数字，本质上是一个排序问题。设数字 $nums$ 中任意两数字的字符串为$x$和$y$，则规定排序判断规则为：

• 若拼接字符串 $x+y > y+x$，则 $x$ “大于” $y$；
• 反之，若 $x+y < y+x$，则 $x$ “小于” $y$；

这里的+号，表示拼接

$x$ “小于” $y$ 代表：排序完成后，数组中 $x$ 应在 $y$ 左边；“大于” 则反之。

根据以上规则，套用任何排序方法对 $nums$ 执行排序即可。

算法流程：

1. 初始化：字符串列表 $strs$，保存各数字的字符串格式；
2. 列表排序：应用以上“排序判断规则”，对 $strs$执行排序；
3. 返回值：拼接 $strs$ 中的所有字符串，并反向。

本文列举 快速排序 和 内置函数 两种排序方法，其他排序方法也可实现。

快速排序：

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def quick_sort(l,r):
            if l >= r:
                return 
            i, j = l, r

            while i <j:
                # 从右向左找，strs[j] 小于 strs[l]的元素
                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j:
                    j -= 1
                
                # 从左向右找 strs[i] 大于 strs[l] 的元素
                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j:
                    i += 1
            
            strs[i],strs[l] = strs[l], strs[i]
            quick_sort(l,i-1)
            quick_sort(i+1,r)
        
        strs = [str(num) for num in nums]
        quick_sort(0,len(strs)-1)

        return ''.join(strs)

内置排序：

需定义排序规则：

• Python 定义在函数 sort_rule(x, y) 中；
• Java 定义为 (x, y) -> (x + y).compareTo(y + x) ；
• C++ 定义为 (string& x, string& y){ return x + y < y + x; } ；

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def sort_rule(x, y):
            a, b = x + y, y + x # 这里的加号代表
            if a > b:
                return 1
            elif a < b:
                return -1
            else:
                return 0
        

        strs = [str(num) for num in nums]
        strs.sort(key= functools.cmp_to_key(sort_rule))
        return ''.join(strs)