程序员面试题精选100题(41)-把数组排成最小的数(算法)

字号:|
2019-09-22    FW.5VV.CN范文网

题目:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。例如输入数组{32,  321},则输出这两个能排成的最小数字32132请给出解决问题的算法,并证明该算法。

分析:这是096月份百度新鲜出炉的一道面试题,从这道题我们可以看出百度对应聘者在算法方面有很高的要求。

这道题其实是希望我们能找到一个排序规则,根据这个规则排出来的数组能排成一个最小的数字。要确定排序规则,就得比较两个数字,也就是给出两个数字mn,我们需要确定一个规则mn哪个更大,而不是仅仅只是比较这两个数字的数值哪个更大。

根据题目的要求,两个数字mn排成的数字mnnm,如果mn<nm,那么我们应该输出mn,也就是m应该排在n的前面,也就是m小于n;反之,如果nm<mnn小于m。如果mn==mnm等于n

接下来我们考虑怎么去拼接数字,即给出数字mn,怎么得到数字mnnm并比较它们的大小。直接用数值去计算不难办到,但需要考虑到的一个潜在问题是m