剑指 Offer45 把数组排成最小的数【排序】
题目描述
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
示例 1:
1 | 输入: [10,2] |
示例 2:
1 | 输入: [3,30,34,5,9] |
提示:
0 < nums.length <= 100
说明:
- 输出结果可能非常大,所以你需要返回一个字符串而不是整数
- 拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0
解题思路
方法一:排序
将numbers数组先转换为String数组,进而对转换后的String 数组进行排序,排序的比较函数为 字符串小的排序在前即(x,y)->(x+y).compareTo(y+x),最终将排序后的String数组依次合并形成最终答案。
实现代码
1 | import java.util.ArrayList; |
复杂度分析
时间复杂度:O(log n), [排序O(log n);其他O(n)]
空间复杂度:O(n)
资料
剑指 Offer45 把数组排成最小的数【排序】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.