PHP求topK算法
in php with 0 comment

PHP求topK算法

in php with 0 comment

晚上在看很久之前收藏的沈剑老师写的topK优化思路,顺手码了会PHP。

说起算法之前刷了几天的leetCode,最近有些忙也没刷了。

记录下几个常见的topK求解:

1.简单粗暴 全部排序之后截取K个内容

$nums = [1,9,9,3,1,4,7,3,7,2,6,9,1,3,5,6];
$k = 5;
rsort($nums);
var_dump(array_slice($nums,0,$k));

// 输出结果
array(5) { [0]=> int(9) [1]=> int(9) [2]=> int(9) [3]=> int(7) [4]=> int(7) } 

时间复杂度 O(n*lg(n))

2.局部排序 每次取出一个最大值,排序N次

$nums = [4,87,2,45,123,65,68,98,9,634];
$k = 2;
function getTopK($nums,$k){
    for($i = 0;$i < $k;$i++){
        $maxIndex = $i;
        for($j = $i;$j < (count($nums) - $i);$j++){
            if($nums[$maxIndex] < $nums[$j]){
                $maxIndex = $j;
            }
        }
        $maxNum = array_splice($nums,$maxIndex,1);
        array_unshift($nums,$maxNum[0]);
    }
    return array_slice($nums,0,$k);
}
var_dump(getTopK($nums,$k));
//array(2) { [0]=> int(123) [1]=> int(634) }

3.堆排序

HAHAHA,这个没看懂怎么建堆,以后会了再补上

4.随机排序

/**
 * 减治法
 * @param $arr
 * @return int
 */
function getTopK($arr,$num){
    $length = count($arr);
    $left_array = [];
    $right_array = [];

    if($length <= 1) return $arr;

    $midNum = $arr[0];
    for($i = 1;$i < $length;$i++){
        if($arr[$i] > $midNum){
            $left_array[] = $arr[$i];
        }else{
            $right_array[] = $arr[$i];
        }
    }

    if(count($left_array) > $num){ //左侧的数量大于N个数,则取左侧数组中最大的N个数即可
        return getTopK($left_array,$num);
    }elseif(count($left_array) < $num){ //左侧的数量少于N个数 则左边的数+中间数+右侧取(N - 左边总数 - 1)个数
        return array_merge($left_array,array($midNum),getTopK($right_array,($num - count($left_array) - 1) ));
    }else{ //如果左侧正好是最大的N个数
        return $left_array;
    }
}
Comments are closed.