漫画：BAT必考题目 （最小的k个数）
最小的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
02 PART
堆和大小顶堆
这道题出自《剑指offer》，是一道非常高频的题目。可以通过排序等多种方法求解。但是这里，我们使用较为经典的大顶堆（大根堆）解法进行求解。因为我知道有很多人可能一脸懵逼，所以，我们先复习一下大顶堆。
首先复习一下堆，堆(Heap)是计算机科学中一类特殊的数据结构的统称，我们通常是指一个可以被看做一棵完全二叉树的数组对象。如果不记得什么是完全二叉树，可以复习这篇：
堆的特性是父节点的值总是比其两个子节点的值大或小。如果父节点比它的两个子节点的值都要大，我们叫做大顶堆。如果父节点比它的两个子节点的值都要小，我们叫做小顶堆。
我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子。
大顶堆，满足以下公式
arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆也一样：
小顶堆，满足以下公式
arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
03 PART
题目分析
上面我们学习了大顶堆，现在考虑如何用大根堆进行求解。
首先，我们创建一个大小为k的大顶堆。假如数组为[4,5,1,6,2,7,3,8]，k=4。大概是下面这样：
我想肯定这里有不知道如何建堆的同学。记住：对于一个没有维护过的堆（完全二叉树），我们可以从其最后一个节点的父节点开始进行调整。这个不需要死记硬背，其实就是一个层层调节的过程。
（从最后一个节点的父节点调整）
（继续向上调整）
（继续向上调整）
建堆+调整的代码大概就是这样：（翻Java牌子）
//建堆。对于一个还没维护过的堆，从他的最后一个节点的父节点开始进行调整。
private void buildHeap(int[] nums) {
//最后一个节点
int lastNode = nums.length - 1;
//记住：父节点 = (i - 1) / 2 左节点 = 2 * i + 1 右节点 = 2 * i + 2;
//最后一个节点的父节点
int startHeapify = (lastNode - 1) / 2;
while (startHeapify >= 0) {
//不断调整建堆的过程
heapify(nums, startHeapify--);
}
}
//调整大顶堆的过程
private void heapify(int[] nums, int i) {
//和当前节点的左右节点比较，如果节点中有更大的数，那么交换，并继续对交换后的节点进行维护
int len = nums.length;
if (i >= len)
return;
//左右子节点
int c1 = ((i << 1) + 1), c2 = ((i << 1) + 2);
//假定当前节点最大
int max = i;
//如果左子节点比较大，更新max = c1;
if (c1 < len && nums[c1] > nums[max]) max = c1;
//如果右子节点比较大，更新max = c2;
if (c2 < len && nums[c2] > nums[max]) max = c2;
//如果最大的数不是节点i的话，那么heapify(nums, max)，即调整节点i的子树。
if (max != i) {
swap(nums, max, i);
//递归处理
heapify(nums, max);
}
}
private void swap(int[] nums, int i, int j) {
nums[i] = nums[i] + nums[j] - (nums[j] = nums[i]);
}
然后我们从下标 k 继续开始依次遍历数组的剩余元素。如果元素小于堆顶元素，那么取出堆顶元素，将当前元素入堆。在上面的示例中 ，因为2小于堆顶元素6，所以将2入堆。我们发现现在的完全二叉树不满足大顶堆，所以对其进行调整。
（调整前）
（调整后）
继续重复上述步骤，依次将7,3,8入堆。这里因为7和8都大于堆顶元素5，所以只有3会入堆。
（调整前）
（调整后）
最后得到的堆，就是我们想要的结果。由于堆的大小是 K，所以这里空间复杂度是O(K)，时间复杂度是O(NlogK)。
根据分析，完成代码：
//java
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0)
return new int[0];
int len = arr.length;
if (k == len)
return arr;
//对arr数组的前k个数建堆
int[] heap = new int[k];
System.arraycopy(arr, 0, heap, 0, k);
buildHeap(heap);
//对后面较小的树建堆
for (int i = k; i < len; i++) {
if (arr[i] < heap[0]) {
heap[0] = arr[i];
heapify(heap, 0);
}
}
//返回这个堆
return heap;
}
private void buildHeap(int[] nums) {
int lastNode = nums.length - 1;
int startHeapify = (lastNode - 1) / 2;
while (startHeapify >= 0) {
heapify(nums, startHeapify--);
}
}
private void heapify(int[] nums, int i) {
int len = nums.length;
if (i >= len)
return;
int c1 = ((i << 1) + 1), c2 = ((i << 1) + 2);
int max = i;
if (c1 < len && nums[c1] > nums[max]) max = c1;
if (c2 < len && nums[c2] > nums[max]) max = c2;
if (max != i) {
swap(nums, max, i);
heapify(nums, max);
}
}
private void swap(int[] nums, int i, int j) {
nums[i] = nums[i] + nums[j] - (nums[j] = nums[i]);
}
}
郑重申明（读我的文章必看）：
- 本系列所有教程都不会用到复杂的语言特性，不需要担心没有学过相关语法，使用各语言纯属本人爱好。
- 作为学术文章，虽然风格可以风趣，但严谨，我是认真的。本文所有代码均在leetcode上进行过测试运行。
- 算法思想才是最重要的。
所以，今天的问题你学会了吗？评论区留下你的想法！
腾讯云开发者
