LeetCode 剑指 Offer 45. 把数组排成最小的数
目录
题目描述
题意分析
给定一个非负整数数组，要把所有数字首尾相接拼成一个字符串，在所有可能的拼接顺序中，返回字典意义上最小的那一个。每个数字必须完整地用上一次，不能拆开、不能省略、不能改动内部数位的顺序，我们唯一能决定的只有这些数字之间的先后次序。
交付形式是字符串而不是数字，这一点很重要。它意味着结果长度可能远超 64 位整数的表示范围，也意味着比较的标准是逐字符的字典序，而不是数值大小。
约束里的关键信号是：所有拼接方案得到的字符串长度完全相同（就是所有数字位数之和），因为不管怎么排，每个数字都要贡献自己的全部数位。等长字符串比大小等价于从左到右逐位比较，谁先出现较小的字符谁就更小。这把「求最小拼接数」从一个数值问题彻底转化成了一个排列的字典序问题，也是后续所有推导的地基。
边界情形：数组只有一个元素时直接返回它的字符串形式；所有元素相同时任何顺序结果都一样；元素中含 0 时要格外小心，比如
[0, 1]的最小拼接是"01"而不是"1"，因为题目要的是拼接串本身，不是它作为数字的规范写法。
解法：字符串拼接比较排序
核心思路
把每个数字转成字符串。对两个字符串
x、y，只有xy和yx两种相邻顺序：
- 若
xy < yx，x应排在y前；- 若
xy > yx，y应排在x前；- 若二者相等，交换它们不会改变最终结果。
因此比较规则是
(x + y).compareTo(y + x)。它也可以理解为比较x、y各自无限重复后的字典序，所以满足传递性，可以安全交给排序算法。正确性可用交换论证说明：若某个排列中相邻的
x、y满足xy > yx，交换后公共前缀和后缀都不变，中间部分从xy变为更小的yx，整个结果一定变小。不断消除这样的逆序对，最终得到按上述规则排序的序列；此时已不存在能让结果变小的相邻交换，因此拼接结果最小。全程在字符串上比较和拼接，既不会发生整数溢出，也会按题意保留前导零。
解题步骤
- 将
nums中每个整数转换为字符串。- 按
x + y < y + x的规则升序排序。- 按排序结果依次拼接并返回。
以
[3, 30, 34, 5, 9]为例："30" + "3" = "303"小于"3" + "30" = "330"，所以30在3前；其余元素同理，排序为[30, 3, 34, 5, 9]，结果是"3033459"。面试时应重点解释为什么不能按数值或普通字典序排序，以及上面的相邻交换为什么保证全局最优。
代码实现
class Solution {
public String minNumber(int[] nums) {
String[] values = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
values[i] = String.valueOf(nums[i]);
}
java.util.Arrays.sort(
values,
(x, y) -> (x + y).compareTo(y + x)
);
StringBuilder answer = new StringBuilder();
for (String value : values) {
answer.append(value);
}
return answer.toString();
}
}
import (
"sort"
"strconv"
"strings"
)
func minNumber(nums []int) string {
values := make([]string, len(nums))
for i, num := range nums {
values[i] = strconv.Itoa(num)
}
sort.Slice(values, func(i, j int) bool {
return values[i]+values[j] < values[j]+values[i]
})
var answer strings.Builder
for _, value := range values {
answer.WriteString(value)
}
return answer.String()
}
复杂度分析
- 时间复杂度：$O(nd \log n)$。
n是数字个数，d是数字的最大位数；排序进行 $O(n \log n)$ 次比较，每次拼接比较最多处理 $O(d)$ 个字符。- 空间复杂度：$O(nd)$。字符串数组和最终结果共保存所有数字的字符；排序还需要至多 $O(n)$ 的辅助空间。
关键点总结
- 比较的不是
x与y，而是xy与yx。- 局部规则能得到全局最优，依据是相邻交换论证。
- 比较器满足传递性；
xy == yx时二者顺序不影响答案。- 结果可能很长且可能有前导零，不能转成整数。
易错点总结
- 按数值升序：
[3, 30]会得到"330"，正确答案是"303"。- 按普通字符串字典序：
"3"会排在"30"前，仍然错误。- 比较器方向写反：
(y + x).compareTo(x + y)求的是最大拼接数。- 把结果转成数值：长结果会溢出，
[0, 1]还会错误地丢掉前导零。- 用
String +=反复拼接：会重复复制已有前缀，应使用StringBuilder。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 179. 最大数 | 中等 | 比较方向相反求最大拼接，且需处理全零输入拼出 "000" 的特判 |
| 451. 根据字符出现频率排序 | 中等 | 比较键来自额外统计出的频次，而不是元素之间的两两拼接 |
| 937. 重新排列日志文件 | 中等 | 多级比较器：先分类字母日志与数字日志，再按内容和标识符依次定序 |
| 1356. 根据数字二进制下 1 的数目排序 | 简单 | 主键是位计数、次键是数值的双关键字排序，比较逻辑无需证明传递性 |