最小的K个数

题目描述

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

解法一：php 函数 sort()

直接用sort()函数排序，再取前k个。

解法二：快速排序

<?php

namespace app\index\controller;

class Test
{
    // 测试
    public function test()
    {
        $input = [4, 5, 1, 6, 2, 7, 3, 8];
        $this->GetLeastNumbers_Solution($input, 4);
    }

    /**
     * @param $input 输入数组
     * @param $k     前k个元素
     */
    public function GetLeastNumbers_Solution($input, $k)
    {
        if ($k > count($input)) return [];
        return array_slice($this->quick_sort($input), 0, $k);  // 截取前k个元素
    }

    /**
     * @title 快速排序
     * @param $input 输入数组
     * @return array 返回数组
     */
    public function quick_sort($input)
    {
        $length = count($input);
        if ($length < 2) return $input;      // 如果是最后一个元素，则直接返回

        $base      = reset($input);          // 取数组第一个元素作为基准
        $left_arr  = [];                     // 存放小于基准的元素
        $right_arr = [];                     // 存放大于基准的元素

        for ($i = 0; $i < $length; $i++) {
            if ($input[$i] < $base)
                $left_arr[] = $input[$i];
            elseif ($input[$i] > $base)
                $right_arr[] = $input[$i];
        }
        // 继续递归左右数组，排好序
        return array_merge($this->quick_sort($left_arr), [$base], $this->quick_sort($right_arr));
    }
}

解法三：最大堆

<?php

namespace app\index\controller;

class Test
{
    // 测试
    public function test()
    {
        $input = [4, 5, 1, 6, 2, 7, 3, 8];
        $this->GetLeastNumbers_Solution($input, 4);
    }

    /**
     * @param $input 输入数组
     * @param $k     前k个元素
     */
    public function GetLeastNumbers_Solution($input, $k)
    {
        if (count($input) < $k) return [];

        $queue = new \SplPriorityQueue();

        foreach ($input as $key => $val) {
            if ($queue->count() < $k) {                // 前k个直接插入
                $queue->insert($key, $val);            // 节点的键为$key，优先值为$val
            } elseif ($input[$queue->top()] > $val) {  // 如果堆顶 > 元素值，则删去堆顶，再添加新节点
                $queue->extract();
                $queue->insert($key, $val);
            }
        }

        $res = [];  // 结果数组
        while (!$queue->isEmpty()) {
            $res[] = $input[$queue->extract()];
        }
        return $res;
    }
}

笔记

SplPriorityQueue 类：使用最大堆实现的优先队列的主要功能。