PHP 计算最小的k个数

PHP 计算最小的k个数

author: he xiaodong date: 2020-05-19
计算最小的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;
    }
}

© 原创文章