LeetCode 剑指 Offer 45. 把数组排成最小的数
题目描述
题意分析
将数组中的每个非负整数视为一个不可拆开的整体，调整它们的先后顺序并拼接，返回能得到的最小字符串。每个输入元素都要使用，重复元素也不能省略。
目标是让完整拼接结果最小，而不是把各个数字按大小排序。所有排列的总位数相同，可以直接比较字符串字典序。结果可能超过整数范围，也允许保留前导零，所以应以字符串返回。
解法：字符串拼接比较排序
核心思路
[!blue]
先决定两个元素怎样排列更好。设它们的字符串为
x、y，只有x + y和y + x两种先后关系；前者较小时就让x在前，相等时先后顺序不影响结果。单独比较x、y的数值或字典序，都没有考虑另一个字符串接在后面时的影响。这个比较规则为什么能用于排序？设两段的数值分别为 $X$、$Y$，长度分别为 $p$、$q$。拼接比较 $X\cdot10^q+Y\le Y\cdot10^p+X$，等价于 $X/(10^p-1)\le Y/(10^q-1)$。因此，这个规则相当于比较每个元素各自确定的大小，具备传递性，不会产生相互矛盾的先后要求。这里只用等式说明性质，实际代码仍直接比较字符串，避免数值溢出。
再看完整结果：如果相邻的
x、y违反上述顺序，把它们交换成更小的拼接后，前缀、后缀和总长度都不变，整个字符串就会变小。把任意排列中的这些逆序不断消除，最终得到按该规则排好的顺序，过程中结果只会减小或保持不变。因此排序后的完整拼接就是全局最小值。按比较器排好所有字符串后，使用可追加的字符串缓冲区顺序连接即可，不需要将拼接结果转回数字。
解题步骤
- 将每个整数转换成字符串，保留所有元素。
- 排序时比较
x + y与y + x，让产生较小拼接的字符串排在前面。- 用
StringBuilder或strings.Builder依次追加排序后的字符串。- 直接返回拼接结果，不删除前导零，也不做整数解析。
代码实现
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(nd)$，用于保存转换后的字符串和拼接结果。比较器临时字符串需要 $O(d)$，排序辅助空间不超过 $O(n)$。
关键点总结
[!green]
- 相邻元素的优劣取决于两种拼接顺序，而非元素本身大小。
- 比较规则具备传递性，才可以由排序形成一致的整体顺序。
- 相邻交换只改变被交换的片段，因此局部改进可以证明最终拼接最小。
- 返回值是字符串，前导零和超出整数范围都不会妨碍构造答案。
易错点总结
[!yellow]
- 按数值或普通字典序排序，都可能误判不同长度数字的先后关系，应比较
xy与yx。- Java 比较器写成
(y + x).compareTo(x + y)会反转目标，得到最大拼接。- 拼接相等时应视为同序：Java 返回零，Go 的严格小于比较返回
false，不能强行判某一方更小。- 把结果解析成整数会丢失前导零，也可能溢出；不能套用最大数题中将全零结果压成单个零的处理。
- 在循环中反复使用不可变字符串
+=会反复复制已有前缀，应使用缓冲区追加。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 179. 最大数 | 中等 | 都用a+b与b+a比较拼接顺序，原题取最大，本题取最小且按题意保留可能的前导0。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！