PHP试题---10W个不同数字组成的数组取出TOP5

落日映苍穹つ 2022-03-11 05:06 133阅读 0赞

昨天去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），当然，我们也可以对上述思路进行一些优化，具体咱就不赘述了。

第二种思路，就简单了，大家可以参考快速排序这个算法：

大家可以看到，快速排序呢会先取出一个基数来作为比较的一个案例，我们就可以参考这个，做出如下改变：

具体思路如下，我们只要快速排序中的比基数大的元素，最后只剩下五个元素，极端情况下，可能基数就是TOP1，这就需要咱们做一个简单的优化了，我感觉还是第一个思路比较保险，无论你的基数出现什么状况都可以取到TOP5。

好啦，本次记录就到这里了，关于这个取出TOP5的方案还有很多，大家有想法的话，可以多多留言来探讨。

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