剑指offer 面试题45. 把数组排成最小的数（中）

考查应聘者解决大数问题的能力。应聘者在面试的时候要意识到，把两个int型的整数拼接起来得到的数字可能会超出int型数字能够表达的范围，从而导致数字溢出。我们可以用字符串表示数字，这样就能简捷地解决大数问题。另外，面试官可能要求面试者将比较规则证明出来。

Question

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

示例 1: 

1
2
输入: [10,2]
输出: "102"
示例 2: 
1
2
输入: [3,30,34,5,9]
输出: "3033459"
提示：0 < nums.length <= 100

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

测试用例

功能测试（输入的数组中有多个数字；输入的数组中的数字有重复的数位；输入的数组中只有一个数字）。 特殊输入测试（表示数组的指针为 nullptr 指针）。

本题考点

本题有两个难点；第一个难点是想出一种新的比较规则来排序一个数组；第二个难点是证明这个比较规则是有效的，并且证明根据这个规则排序之后，把数组中所有数字拼接起来得到的数字是最小的。要想解决这两个难点，要求应聘者有很强的数学功底和逻辑思维能力。 考查应聘者解决大数问题的能力。应聘者在面试的时候要意识到，把两个int型的整数拼接起来得到的数字可能会超出int型数字能够表达的范围，从而导致数字溢出。我们可以用字符串表示数字，这样就能简捷地解决大数问题。

Intuition

基本思想

  • 此题求拼接起来的 “最小数字” ，本质上是一个排序问题。
  • 排序判断规则： 设 \(x\) 和 \(y\) 为 \(nums\) 任意两数字的字符串格式，则：
    • 若拼接字符串 \(x + y > y + x\)，则 \(x > y\)，即 \(y\) 应该放到 \(x\) 前面。例如，当 \(x=3\) 和 \(y=30\) 时，\(x + y=330\)，\(y + x=303\)，即 \(x + y > y + x\)，则 \(x > y\)，即 \(y\) 应该放到 \(x\) 前面；
    • 反之，若 \(x + y < y + x\)，则 \(x < y\)，即 \(x\) 应该放到 \(y\) 前面。例如，当 \(x=50\) 和 \(y=80\) 时，\(x + y=5080\)，\(y+x=8050\)，有 \(x + y < y + x\)，则 \(x < y\)，即 \(x\) 应该放到 \(y\) 前面；
  • 根据以上规则，套用任何排序方法对 \(nums\) 执行排序即可。
  • 考虑到结果溢出的问题，一般都需要将 Int 类型数字转换成 list 类型数组，但是这道题由于不做加减法，只做 Int 类型数字的拼接，所以用 Str 类型表示 Int 类型来防止溢出就可以了。

算法流程

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

复杂度分析

时间复杂度 \(O(N \log N)\) ： \(N\) 为最终返回值的字符数量（ \(strs\) 列表的长度 \(\leq N\)）；使用快排或内置函数的平均时间复杂度为 \(O(N \log N)\) ，最差为 \(O(N^2)\)。 空间复杂度 \(O(N)\) ： 字符串列表 \(strs\) 占用线性大小的额外空间。

Code

  • 基于内置的 sort 和 functools.cmp_to_key 函数。
1
2
3
4
5
6
7
8
9
10
11
import functools
class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def compare(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(compare))
        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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def compare(x, y):
            a, b = x + y, y + x
            if a > b:
                return 1  # x > y，即 y 应该放到 x 前面。
            elif a < b:
                return -1  # x < y，即 x 应该放到 y 前面。
            else:
                return 0  # x = y
        
        def quickSort(left, right):
            if left >= right:
                return
            i, j, key = left, right, nums[left]
            while i < j:
                while i < j and compare(nums[j], key) in [1, 0]:  # nums[j] >= key
                    j -= 1
                while i < j and compare(nums[i], key) in [-1, 0]:  # nums[i] <= key
                    i += 1
                nums[i], nums[j] = nums[j], nums[i]
            nums[i], nums[left] = nums[left], nums[i]
            quickSort(left, i-1)
            quickSort(i+1, right)
                
        # 通过不了[1, 4, 7, 2, 5, 8, 0, 3, 6, 9]的TestCase
        def quickSort_V1(nums, left, right):
            if left >= right:
                return
            i, j, key = left, right, nums[left]
            while i < j:
                while i < j and compare(nums[j], key) in [-1, 0]:  # nums[j] >= key
                    j -= 1
                if i < j:
                    nums[i] = nums[j]
                    i += 1
                while i < j and compare(nums[i], key) in [1, 0]:  # nums[i] <= key
                    i += 1
                if i < j:
                    nums[j] = nums[i]
                    j -= i
            
            nums[i] = key
            quickSort(nums, left, i-1)
            quickSort(nums, i+1, right)

        if len(nums) == 0: return ""
        if len(nums) == 1: return str(nums[0])
        nums = [str(num) for num in nums]
        quickSort(0, len(nums)-1)

        return "".join(nums)

    
class TestSolution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()

    def test_solution(self):
        inputs = [
            [1, 4, 7, 2, 5, 8, 0, 3, 6, 9],  # 功能测试
            [10, 2],                         # 功能测试
            [3, 30, 34, 5, 9],               # 功能测试
                                             # 边界值的测试
            []                               # 特殊样例
        ]
        answers = ["0123456789", "102", "3033459", ""]
        res = []
        for i in range(len(inputs)):
            res.append(self.test_class.minNumber(inputs[i]))
        self.assertEqual(res, answers)
 
    def tearDown(self):
        del self.test_class


if __name__ == "__main__":
    unittest.main()

Python Trick

functools.cmp_to_key

将老式的比较函数（comparison function）转化为关键字函数（key function）。与接受 key function 的工具一同使用（如 sorted(), min(), max(), heapq.nlargest(), itertools.groupby())。该函数主要用来将程序转成 Python 3 格式的，因为 Python 3 中不支持比较函数。比较函数是可调用的，接受两个参数，比较这两个参数并根据他们的大小关系返回负值、零或正值中的某一个。关键字函数也是可调用的，接受一个参数，同时返回一个可以用作排序关键字的值。