《剑指Offer》-40.最小的k个数

题干

输入n个整数，找出其中最小的k个数。例如，输入4、5、1、6、2、7、3、8这8个数，则最小的4个数字是1、2、3、4。

解题思路

思路一

使用 Partition 函数的思想，使用第k个数作为哨兵，将数组分为小于第k个数的数字和大于第k个数的数字，如果此时划分后刚好得到前半部分的长度等于k，则找到最小的k个数，如果长度大于k，则在前半部分中继续划分，如果长度小于k，则在后半部分继续划分，直到找到最小的k个数。

思路二

创建一个大小为k的大顶堆存储最小的k个数字，使用前k个数字填充满大顶堆，后续遇到小于顶点的数字时替换大顶堆的顶点，并维护其成为大顶堆，如果遇到大于顶点的数字则直接跳过。

维护大顶堆的时间复杂度是O(logk)，所以对于求n个数字中的最小的k个数字的时间复杂度就是O(n*logk)。

代码实现

思路一

<?php
/**
 * 使用Partition求最下的k个数
 */


/**
 * @param array $numbers
 * @param int $k
 */
function getLeastNumbers(array $numbers, int $k)
{
    if (empty($numbers) || $k > count($numbers) || $k <= 0) {
        return;
    }
    $start = 0;
    $len = count($numbers);
    $end = $len - 1;
    $index = partition($numbers, $k, $start, $end);
    while ($index != $k - 1) {
        if ($index < $k - 1) {
            $start = $index + 1;
            $index = partition($numbers, $k, $start, $end);
        } else {
            $end = $index - 1;
            $index = partition($numbers, $k, $start, $end);
        }
    }

    return array_slice($numbers, 0, $k);
}

function partition(&$numbers, $k, $start, $end)
{
    $num = $numbers[$k];
    $i = $start;
    $j = $end;
    while ($i < $j) {
        if ($numbers[$i] < $num) {
            $i++;
        }
        if ($numbers[$j] > $num) {
            $j--;
        }
        $tmp = $numbers[$i];
        $numbers[$i] = $numbers[$j];
        $numbers[$j] = $tmp;
    }

    return $i;
}

$numbers = [4, 5, 1, 6, 2, 7, 3, 8];
$res = getLeastNumbers($numbers, 6);
var_dump($res);