欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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的方案还有很多,大家有想法的话,可以多多留言来探讨。

如果感觉不错的话,请多多点赞支持哦。。。