PHP试题---10W个不同数字组成的数组取出TOP5
程序员文章站
2024-03-15 20:28:36
...
昨天去OFasion面试,与面试官有一个如下算法试题,咱们这里来讨论沟通下:
$arr = array(3,5,7,8,1,2,456,78,...101,2345,456);
类似上述数组,共有十万个元素,让我们取出TOP5,这个先来看下我给出的方案。
首先,取出上述数组的前五个元素,与上述数组组成如下两个数组:
$arr_1 = array(3,5,7,8,1);
$arr_2 = array(2,456,78,...101,2345,456);
完事可以进行如下处理:
for($big=0;$big<9995;$big++){
for($little=0;$little < 5;$little++){
if($arr_2[$big] > $arr_1[$little]){
$arr_1[$little] = $arr_2[$big];
break;
}
}
}
var_dump($arr_1);
具体的思路就是,先去出来五个元素,完事循环进行比较,如果大数组的元素大于小数组中的任意一个元素,则替换,完事跳出当前循环,这个思路的时间空间复杂度不到O(N*N),当然,我们也可以对上述思路进行一些优化,具体咱就不赘述了。
第二种思路,就简单了,大家可以参考快速排序这个算法:
function quickSort($arr) {
$length = count($arr);
if($length <= 1) {
return $arr;
}
$base_num = $arr[0];
$left_array = array();
$right_array = array();
for($i=1; $i<$length; $i++) {
if($base_num > $arr[$i]) {
$left_array[] = $arr[$i];
} else {
$right_array[] = $arr[$i];
}
}
$left_array = quick_sort($left_array);$right_array = quick_sort($right_array);
return array_merge($left_array, array($base_num), $right_array);
}
大家可以看到,快速排序呢会先取出一个基数来作为比较的一个案例,我们就可以参考这个,做出如下改变:
function quickSort($arr) {
$length = count($arr);
if($length = 5) {
return $arr;
}
$base_num = $arr[0];
$big_array = array();
for($i=1; $i<$length; $i++) {
if($base_num < $arr[$i]) {
$big_array[] = $arr[$i];
}
}
$big_array = quick_sort($big_array);
return $big_array;
}
具体思路如下,我们只要快速排序中的比基数大的元素,最后只剩下五个元素,极端情况下,可能基数就是TOP1,这就需要咱们做一个简单的优化了,我感觉还是第一个思路比较保险,无论你的基数出现什么状况都可以取到TOP5。
好啦,本次记录就到这里了,关于这个取出TOP5的方案还有很多,大家有想法的话,可以多多留言来探讨。
如果感觉不错的话,请多多点赞支持哦。。。