【剑指offer】032-把数组排成最小的数

题目

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。

方法

方法:排序 —— 修改排序规则
参考:https://blog.csdn.net/dawn_after_dark/article/details/81256350
时间复杂度:排序的时间复杂度

思路

假如数组只有2个元素a和b。可以组合成ab和ba,存在下面的排序规则的:
如果ab < ba,那么取ab
如果ab > ba,那么取ba
如果ab = ba,取ab或ba都行

那么如果数组不止2个元素,但是针对数组中任意2个元素,在组合和的位置中,也是可以套用上面的排序规则的。比如有3个元素a、b和c。那么如果c一直在中间,可以组成acb,和acb
如果acb < bca,那么取acb
如果acb > bca,那么取bca
如果acb = bca,取acb或bca都行

按照上述例子,数字中任意2个元素在组合后的顺序是符合一开始的排序规则的,那么就可以通过排序数组的元素,替换掉比较规则为上述的排序规则,最后将排序后的数组各元素直接拼接起来,即可得到答案

代码

1
2
3
4
5
6
7
8
9
function PrintMinNumber (numbers) {
// write code here
numbers.sort((a, b) => {
let ab = Number(new String(a) + new String(b))
let ba = Number(new String(b) + new String(a))
return ab > ba
})
return numbers.join('')
}
文章作者: ptp
文章链接: https://youyingjie114.github.io/2019/11/07/jz-offer/jz-offer-032/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 PTP'S BLOG