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

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

2022年8月27日

---

一、问题描述

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

示例 1:

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

示例 2:

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

提示:

0 < nums.length <= 100
1

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

二、问题分析

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

(1) 若拼接字符串 x + y > y + x ，则 x “大于” y ；
(2) 反之，若 x + y < y + x ，则 x “小于” y ；
(3) x “小于” y 代表：排序完成后，数组中 x 应在 y 左边；“大于” 则反之。

• 根据以上规则，套用任何排序方法对 nums 执行排序即可，这里使用快速排序。
  

三、解题代码

class Solution(object):
    def minNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        def quick_sort(l, r):
            if l > r:
                return
            i, j = l, r
            while i < j:
                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: j -= 1
                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: i += 1
                strs[i], strs[j] = strs[j], strs[i]
            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(nums)-1)

        return ''.join(strs)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

总结

将该问题转化为字符串排序的问题，在执行任意排序算法即可，这里使用了快速排序。