计算最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
限制：
- 0 <= k <= arr.length <= 10000
- 0 <= arr[i] <= 10000
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
解题思路
直接使用最大堆，堆的大小为 k，这样保证空间占用最小，最小堆的根节点是就是最小值，也是我们想要的结果。PHP 的 SPL 标准库是有最大堆这个库，直接在代码中继承 SplMinHeap 。
PHP 实现
class Solution {
/**
* @param Integer[] $arr
* @param Integer $k
* @return Integer[]
*/
function getLeastNumbers($arr, $k) {
$heap = new SplMaxHeap();
foreach ($arr as $key => $val) {
if ($heap->count() < $k) {
$heap->insert($val);
} elseif ($heap->valid() && $heap->top() > $val) {
// 当堆满的时候，比较要插入元素和堆顶元素大小。小于堆顶的插入。堆顶移除。
$heap->extract();
$heap->insert($val);
}
}
$minArray = [];
for ($i = 0; $i < $k; $i++) {
if ($heap->valid()) {
$minArray[] = $heap->top();
$heap->next();
}
}
return $minArray;
}
}
© 原创文章
