2020-05-19-PHP 计算最小的k个数

layout: posttitle: PHP 计算最小的k个数
subtitle: PHP 计算最小的k个数
date: 2020-05-19
author: he xiaodong
header-img: img/default-post-bg.jpg
catalog: true
tags:
- Go
- PHP
- LeetCode
- 计算最小的k个数

计算最小的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;
    }
}

© 原创文章

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券