从数组中查找最小的k个元素PHP版

PHP ,

答案

思路:

  1. 假设最前面的1000个数为最小的,算出这1000个数中最大的数,然后和第1001个数比较
  2. 如果这个最大的数比第1001个数小的话,跳过
  3. 如果这个最大的数比第1001个数大则将两个数交换位置,并算出新的1000个数里面的最大数
  4. 再和下一个数比较,以此类推
/**
 * 从数组里找出最小的 $k 个数
 * @param $arr array 输入数组
 * @param $k int 输出元素个数
 * @return array 最小元素集合
 */
function getMinK($arr, $k)
{
    $n = count($arr);
    $minArray = array();

    for ($i = 0; $i < $n; $i++) {
        if ($i < $k) {
            $minArray[$i] = $arr[$i];
        } else {
            if ($i == $k) {
                $maxPos = getMaxPos($minArray);
                $max = $minArray[$maxPos];
            }
            if ($arr[$i] < $max) {
                $minArray[$maxPos] = $arr[$i];
                $maxPos = getMaxPos($minArray);
                $max = $minArray[$maxPos];
            }
        }
    }

    return $minArray;
}

/**
 * 从数组中查找最大值的位置
 * @param $arr array 待查找数组
 * @return int 位置
 */
function getMaxPos($arr)
{
    $pos = 0;
    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] > $arr[$pos]) {
            $pos = $i;
        }
    }

    return $pos;
}

测试代码:

$arr = [1, 100, 20, 22, 33, 44, 55, 66, 23, 79, 18, 20, 11, 9, 129, 399, 145, 2469, 58];
$res = getMinK($arr, 5);

// 输出:[1,9,20,11,18]
echo json_encode($res);

发表评论

电子邮件地址不会被公开。 必填项已用*标注

昵称 *