可视化图解算法50：最小的K个数

牛客网面试笔试 TOP101 | LeetCode 面试题 17.14. 最小K个数

1. 题目

描述

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。

数据范围：0≤k,n≤10000，数组中每个数的大小0≤val≤1000

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

示例1

输入：

[4,5,1,6,2,7,3,8],4

返回值：

[1,2,3,4]

说明：

返回最小的4个数即可，返回[1,3,2,4]也可以

示例2

输入：

[1],0

返回值：

[ ]

示例3

输入：

[0,1,2,1,2],3

返回值：

[0,1,1]

2. 解题思路

最小的K个数的求解问题是典型的Top K问题，一般通过堆来完成。先来看看什么是堆：

堆" 是一个在计算机科学中经常使用的术语，它通常指的是一种特殊的树形数据结构——二叉堆（binary heap）。二叉堆通常满足堆属性（heap property），即父节点的值总是大于或等于（或小于或等于，取决于堆的类型）其子节点的值。

堆是一种完全二叉树结构，并满足以下性质之一：

最大堆（Max-Heap）：每个父节点的值大于或等于其子节点的值。

最小堆（Min-Heap）：每个父节点的值小于或等于其子节点的值。

核心特性

完全二叉树：

除了最后一层，其他层节点全部填满，且最后一层节点尽可能靠左排列。

高效操作：

插入和删除操作的时间复杂度为 O(log n)，建堆时间复杂度为 O(n)。

堆的存储方式
数组实现（最常用）：

父节点索引为 i，则左子节点为 2i+1，右子节点为 2i+2。

子节点索引为 i，则父节点为 (i-1)//2。
示例

（数组表示的堆）：
<span style="background-color:#f8f8f8 !important">数组：[9, 5, 3, 2, 4, 1]
对应完全二叉树：9/   \5     3/ \   /2  4 1
堆的应用场景

优先队列：任务调度、Dijkstra 算法。

堆排序：时间复杂度 O(n log n)，原地排序但不稳定。

Top K 问题：快速找到数据流中最大/最小的 K 个元素。

合并有序序列：如合并 K 个有序链表。

堆（Heap）是一种特殊的树形数据结构，通常以完全二叉树的形式实现，具有以下核心特性：

常见误区

堆与内存堆：

数据结构中的“堆”与程序内存管理中的“堆”（Heap Memory）完全不同。

堆的有序性：

堆仅保证根节点是极值，子树之间不一定有序。

如果文字描述的不太清楚，你可以参考视频的详细讲解。

Python编码：Python数据结构LeetCode笔试面试算法_哔哩哔哩_bilibiliPython数据结构LeetCode笔试面试算法,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1372869
Java编码：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1367923
Golang编码：LeetCode数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1364949

3. 编码实现

核心代码如下：

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param input int整型一维数组* @param k int整型* @return int整型一维数组*/
func GetLeastNumbers_Solution(input []int, k int) []int {// write code hereres := make([]int, 0)if k == 0 || len(input) < k {return res}//1.定义一个大顶堆（最大元素在最上面）h := make(MyHeap, 0, k)heap.Init(&h)//2.先将k个元素加入堆for i := 0; i < k; i++ {heap.Push(&h, input[i])}//3.如果当前元素小于堆顶的元素（待加入的元素比堆中的小）则将堆中的最大元素弹出，新元素入堆//弹出的作用：保证堆中只存储最小的k个数据for i := k; i < len(input); i++ {if input[i] < h[0] {heap.Pop(&h)heap.Push(&h, input[i])}}//4.堆中的元素弹出，存储到数组中返回for h.Len() > 0 {res = append(res, heap.Pop(&h).(int))}return res
}

具体完整代码你可以参考下面视频的详细讲解。

Python编码：Python数据结构LeetCode笔试面试算法_哔哩哔哩_bilibiliPython数据结构LeetCode笔试面试算法,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1372869
Java编码：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1367923
Golang编码：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364949

4.小结

最小的K个数可以通过大顶堆完成，具体操作步骤为：

定义一个大顶堆，堆的大小为 K；
堆中存储最小的K个数；
先从数组中取出 K 个元素加入堆；
再从数组中取出其他元素，如果该元素小于堆顶的元素，从堆中弹出元素，将该元素加入堆；
数组中的元素取完，堆中的数据就是最小的K个数。

《数据结构与算法》深度精讲课程正式上线啦！7 大核心算法模块全解析：

✅ 链表

✅ 二叉树

✅ 二分查找、排序

✅ 堆、栈、队列

✅ 回溯算法

✅ 哈希算法

✅ 动态规划

无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！

Python编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ss897667807
Java编码实现：LeetCode数据结构笔试面试算法-Java版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Java版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss161443488
Golang编码实现：LeetCode数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss63997