正文
PHP 十万数字不同数组取最大的5个 (经典面试题topK) (原)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
$arr = array(3,5,7,8,1,2,456,78,...101,2345,456);
类似上述数组，共有十万个元素，让我们取出TOP5，下面是我的解法,先上代码再讲解思路
function topk($arr)
{
//取十万数组的前五个元素组成升序数组
$result = sort(array_slice($arr,0,5));
for($i=5;$i<100000;$i++){
for($j=4;$j>=0;$j--){
if($result[$j]<$arr[$i]){
$result[$j] = $arr[$i];
unset($result[0]);
}
}
}
}
具体思路是,拿出前五个元素组成升序队列,将数组剩下的元素与该升序队列进行循环比较,若大于小数组任一元素,则替换该元素,并删除小数组最小的元素
还有一种思路呢,是按冒泡排序,十万数字走五次,取最后五个元素就是数组的top5,
-----------------------------------------------END-------------------------------------------------------------------------------
时间复杂度希望有人能帖一下~
如果有发现错误的地方麻烦留言告知,让我能及时修正哟 感谢~
