《剑指Offer》-40.最小的k个数

题干

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


©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 前言 2. 实现 Singleton 3. 数组中重复的数字 4. 二维数组中的查找 5. 替换空格 6. 从尾到...
    Observer_____阅读 3,008评论 0 1
  • 第一章 绪论 什么是数据结构? 数据结构的定义:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章...
    SeanCheney阅读 5,828评论 0 19
  • 今日体验:今天端午节并且提前下班了,回来的都挺早的,上午的时候在群里玩红包挺开心的,核心:与同事们之间的快乐,总结...
    房傲东阅读 187评论 0 0
  • 熟悉本行业内所有关于产品和大型企业的知识和内容,主要包括龙头行业、自己所要销售产品的优势和不足等; 知道并了解所要...
    旧时浮尘_794c阅读 846评论 2 0
  • 今晚看到在写作文,他一头雾水。不知从何写起,看着都很心痛。平时少陪他看课外书,是做父母的错。以后会多陪你看书的,把...
    清风NO1阅读 152评论 0 0