最大数:数组拼接成最大的数(LC179)
哪些公司问过
答案要点
- 整数转字符串,按 a+b 与 b+a 的大小决定先后顺序
- 排序后依次拼接即为最大数,示例结果为 9534330
- 该比较关系具有传递性,可作为合法的排序比较器
- 复杂度 O(k·n log n),k 为平均位数,空间 O(n)
- 处理全零输入:排序后首元素为 0 时直接返回 0
易错点
- 直接按字符串字典序降序排序
- 全零输入返回 000 而不是 0
- 把拼接结果转成整数比较导致溢出
- C++ 比较器写成大于等于,违反严格弱序
面试官常见追问
- 为什么不能直接按字典序降序排?
- 比较器写成大于等于会怎样?
- 怎么证明比较规则有传递性?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场