跳至主要內容

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

ITCharge大约 2 分钟

剑指 Offer 45. 把数组排成最小的数open in new window

  • 标签:贪心、字符串、排序
  • 难度:中等

题目链接

题目大意

描述:给定一个非负整数数组 numsnums

要求:将数组中的数字拼接起来排成一个数,打印能拼接出的所有数字中的最小的一个。

说明

  • 0<nums.length1000 < nums.length \le 100
  • 输出结果可能非常大,所以你需要返回一个字符串而不是整数。
  • 拼接起来的数字可能会有前导 00,最后结果不需要去掉前导 00

示例

  • 示例 1:
输入: [10,2]
输出: "102"
  • 示例 2:
输入:[3,30,34,5,9]
输出:"3033459"

解题思路

思路 1:自定义排序

本质上是给数组进行排序。假设 xxyy 是数组 numsnums 中的两个元素。则排序的判断规则如下所示:

  • 如果拼接字符串 x+y>y+xx + y > y + x,则 xx 大于 yyyy 应该排在 xx 前面,从而使拼接起来的数字尽可能的小。
  • 反之,如果拼接字符串 x+y<y+xx + y < y + x,则 xx 小于 yyxx 应该排在 yy 前面,从而使拼接起来的数字尽可能的小。

按照上述规则,对原数组进行排序。这里使用了 functools.cmp_to_key 自定义排序函数。

思路 1:自定义排序代码

import functools

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def cmp(a, b):
            if a + b == b + a:
                return 0
            elif a + b > b + a:
                return 1
            else:
                return -1

        nums_s = list(map(str, nums))
        nums_s.sort(key=functools.cmp_to_key(cmp))
        return ''.join(nums_s)

思路 1:复杂度分析

  • 时间复杂度O(n×logn)O(n \times \log n)。排序算法的时间复杂度为 O(n×logn)O(n \times \log n)
  • 空间复杂度O(1)O(1)

参考资料