输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。
要求打印出最小的排列顺序,最简单粗暴的方式就是利用字符串排列那样将所有的情况全部遍历出来,然后在比较大小。但是事件会非常非常长,占用的空间非常大,所以应该放弃。题目的实质对数组的排序。排序的方法不是关键,关键的是规则。之前曾经比较的规则考虑的复杂化,自认为对两个元素进行每一位比较,而且不简单的时字符串大小比较,总是没有通过。后来恍然大悟,我可以将两个数进行排列,得到两种情况,对这两种情况得到的新数进行比较大小就可以判断如何排列组合能够使得两个数拼接得到的第三个数最小,从而制定排序规则。代码如下:
function PrintMinNumber($numbers)
{
// write code here
for($i=0;$i<count($numbers);$i++){
for($j=0;$j<count($numbers)-1-$i;$j++){
if(rule($numbers[$j],$numbers[$j+1])){
$t = $numbers[$j];
$numbers[$j] = $numbers[$j+1];
$numbers[$j+1] = $t;
}
}
}
return implode("",$numbers);
}
function rule($one,$other){
$one = "$one";
$other = "$other";
$a = $one.$other;
$b = $other.$one;
return $a > $b;
}