在数组操作类算法中，“将正整数数组拼接成最小数字”是一道经典题目，其核心难点在于突破常规排序思维，设计符合需求的比较规则。本文将从问题分析入手，解析自定义排序的原理，提供Python与C++实现代码，并验证算法正确性，帮助深入理解此类问题的解决思路。

问题描述

输入一个正整数数组，将数组中所有数字拼接成一个新整数，要求找到并打印出其中最小的那个整数。
示例：输入数组[3, 32, 321]，所有可能的拼接结果为332321、332132、323321、323213、321332、321323，其中最小的数字是321323，因此输出"321323"。

核心难点与常规方案局限

若采用“全排列”思路，枚举所有数字的拼接组合后筛选最小值，虽能得到正确结果，但时间复杂度为O(n!)（n为数组长度）。当n≥10时，10! = 3628800，计算量会急剧增加，导致效率严重低下，无法应对较大规模的输入。

因此，需要一种更高效的方法——通过自定义排序规则，直接确定数字的最优拼接顺序，将时间复杂度降至O(n log n)（排序算法的时间复杂度）。

关键思路：自定义排序规则

规则设计依据

两个数字a和b拼接时，只有两种可能的组合：ab（a在前b在后）和ba（b在前a在后）。要使最终拼接结果最小，需优先选择“组合后更小”的顺序，即：

若ab < ba：a应排在b前面（如32和321，32321 > 32132，故321排在32前）
若ab > ba：b应排在a前面
若ab = ba：a和b顺序可互换

由于数字拼接后可能超出整数范围（如大数组拼接），直接转换为整数比较会导致溢出，因此先将数字转换为字符串，通过字符串字典序比较拼接结果（字符串字典序比较与数字大小比较逻辑一致，且无溢出风险）。

规则合理性证明

自定义排序规则需满足“传递性”，才能保证排序结果的有效性（即若a应排在b前，b应排在c前，则a应排在c前）：假设ab ≤ ba且bc ≤ cb，需证明ac ≤ ca。
由于字符串拼接满足结合律，(ab)c = a(bc)，(ba)c = b(ac)，a(cb) = (ac)b，b(ca) = (bc)a。结合ab ≤ ba和bc ≤ cb，可推导出ac ≤ ca，因此规则满足传递性，排序结果有效。

代码实现

Python版本（适配Python 2/3，处理兼容性）

原链接中Python代码使用cmp参数（Python 2内置，Python 3需通过functools.cmp_to_key转换），以下提供兼容版本：

# -*- coding:utf-8 -*-
from functools import cmp_to_key  # 用于Python 3中将cmp函数转换为key函数

class Solution:
    def PrintMinNumber(self, numbers):
        # 处理空数组边界 case
        if not numbers:
            return ""
        
        # 1. 定义比较函数：按拼接后字符串的字典序比较
        def compare(a, b):
            # 将数字转换为字符串后拼接
            ab = str(a) + str(b)
            ba = str(b) + str(a)
            # 返回值：<0 则a排在b前，>0 则b排在a前，=0 则顺序不变
            if ab < ba:
                return -1
            elif ab > ba:
                return 1
            else:
                return 0
        
        # 2. 按自定义规则排序数组
        # Python 3中sorted无cmp参数，需用cmp_to_key转换
        sorted_nums = sorted(numbers, key=cmp_to_key(compare))
        
        # 3. 将排序后的数组元素拼接为字符串并返回
        return ''.join(str(num) for num in sorted_nums)

C++版本（保留原链接核心逻辑，补充注释）

#include <vector>
#include <string>
#include <algorithm>  // 用于sort函数

using namespace std;

class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        int length = numbers.size();
        // 处理空数组边界 case
        if (length == 0) {
            return "";
        }
        
        // 1. 按自定义比较规则排序：cmp为静态成员函数（非静态成员函数需依赖对象，无法被sort调用）
        sort(numbers.begin(), numbers.end(), cmp);
        
        // 2. 拼接排序后的数字为字符串
        string result;
        for (int num : numbers) {  // 范围for循环，遍历数组
            result += to_string(num);  // 数字转字符串后拼接
        }
        
        return result;
    }

private:
    // 静态成员函数：自定义比较规则（sort要求比较函数为全局函数或静态成员函数）
    static bool cmp(int a, int b) {
        // 数字转字符串，避免拼接溢出
        string str_a = to_string(a);
        string str_b = to_string(b);
        
        // 比较拼接后的字符串字典序
        string ab = str_a + str_b;
        string ba = str_b + str_a;
        
        // 若ab < ba，返回true表示a应排在b前（sort默认升序）
        return ab < ba;
    }
};

代码验证与分析

以示例numbers = [3, 32, 321]为例，逐步验证执行流程：

排序前：数组为[3, 32, 321]
比较过程：
比较3和32："332" > "323" → 32排在3前
比较32和321："32321" > "32132" → 321排在32前
比较3和321："3321" > "3213" → 321排在3前
排序后：数组为[321, 32, 3]
拼接结果："321" + "32" + "3" = "321323"，与示例预期一致。

算法复杂度分析

时间复杂度：O(n log n)，核心为排序操作（n为数组长度），每个元素的比较操作（字符串拼接与比较）时间为O(k)（k为数字平均位数，可视为常数），因此整体复杂度为O(n log n)。
空间复杂度：O(nk)，用于存储排序过程中产生的字符串（如拼接后的ab和ba），最坏情况下需存储n个长度为2k的字符串，空间复杂度为O(nk)。

边界 case 处理

空数组：返回空字符串（如numbers = []，输出""）
单元素数组：直接返回该元素的字符串形式（如numbers = [5]，输出"5"）
含相同数字的数组：如numbers = [11, 111]，"11111" = "11111"，顺序可互换，最终拼接结果均为"11111"

总结

“把数组排成最小的数”的核心是跳出常规排序思维，设计基于拼接结果的自定义排序规则。通过字符串拼接避免数字溢出，利用排序算法将时间复杂度优化至O(n log n)，是解决此类“最优排列”问题的典型思路。

上述代码简洁高效，同时处理了空数组、大数字溢出等边界情况，可直接用于刷题或工程场景。掌握这种“自定义规则排序”的思想，还能解决类似问题（如“拼接最大数字”“按特定规则排列字符串”等）。

醋醋百科网

Good Luck To You!

把数组排成最小的数:自定义排序规则的应用与实现