32 把数组排成最小的数

题目描述

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

示例：

输入: [3, 32, 321]
输出: "321323"（32132 < 32321）

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

解题思路

核心思想：自定义排序规则。如果拼接后的数更小，则应该排在前面。

关键步骤：

1. 将数字转为字符串
2. 自定义比较函数：如果a+b < b+a，则a应该排在b前面
3. 排序后拼接

时间复杂度：O(n log n) 空间复杂度：O(n)

Python 实现

def print_min_number(nums):
    """
    把数组排成最小的数

    Args:
        nums: 正整数数组

    Returns:
        str: 最小的拼接数
    """
    if not nums:
        return ""

    # 转为字符串
    strs = list(map(str, nums))

    # 自定义排序
    strs.sort(key=lambda x: x, cmp=lambda a, b: -1 if a + b < b + a else (1 if a + b > b + a else 0))

    # 处理前导零的情况
    if strs[0] == "0":
        return "0"

    return ''.join(strs)


# Python 3 兼容版本
def print_min_number_py3(nums):
    """
    Python 3 兼容版本（使用functools.cmp_to_key）
    """
    if not nums:
        return ""

    from functools import cmp_to_key

    strs = list(map(str, nums))

    def compare(a, b):
        if a + b < b + a:
            return -1
        elif a + b > b + a:
            return 1
        else:
            return 0

    strs.sort(key=cmp_to_key(compare))

    if strs[0] == "0":
        return "0"

    return ''.join(strs)


# 测试代码
if __name__ == "__main__":
    test_cases = [
        [3, 32, 321],
        [10, 2],
        [1, 2, 3, 4, 5],
        [0, 0, 0],
    ]

    for nums in test_cases:
        print(f"{nums} → {print_min_number_py3(nums)}")

# 输出:
# [3, 32, 321] → 321323
# [10, 2] → 102
# [1, 2, 3, 4, 5] → 12345
# [0, 0, 0] → 0

图解

示例: [3, 32, 321]

转为字符串: ["3", "32", "321"]

比较排序:
compare("3", "32"):
  "332" < "323"? 否
  "332" > "323"? 是 → 3应该排在32后面

compare("3", "321"):
  "3321" < "3213"? 是 → 3应该排在321前面

compare("32", "321"):
  "32321" < "32132"? 是 → 32应该排在321前面

排序结果: ["321", "32", "3"]

拼接: "32132" < "32321" ✓

最终结果: "321323"