题干
输入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);
