面试题 17.14.最小K个数
题目：如下图
答案：如下图
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void AdjustDown(int* a,int n,int root)
{
int parent = root;
int child = parent * 2 + 1;
//默认左孩子是大的，将其与右孩子比较，如果小于右节点则换
while (child<n)
{
//变号找小的
if (child + 1 < n && a[child] < a[child + 1])
{
++child;
}
//parent永远不可能为负数，c语言是取整运算（-1）/2=0，
// 此时parent=child=0，其a[child]=a[parnet]，执行break
if (a[parent] < a[child])
{
//交换
int tmp = a[parent];
a[parent] = a[child];
a[child] = tmp;
//向下进行迭代
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//TopK问题，先建大堆，比较，返回
int* smallestK(int* arr, int arrSize, int k, int* returnSize) {
//判空
*returnSize = k;
//开辟返回数组指针
int* retArr =(int*)malloc(sizeof(int) * k);
if (k==0)
{
return retArr;
}
//将arr中的元素复制到retArr中
for (int i = 0; i < k; ++i)
{
retArr[i] = arr[i];
}
//向下调整retArr为大堆,并且大堆中的元素个数为k个,第一次见
for (int i = (k-1-1)/2 ; i>=0; --i)
{
//字面意思就行
//向下调整一调整就是“垂直”的整个路径
AdjustDown(retArr, k, i);
}
//比较并且重新赋值?
for (int j = k; j < arrSize; ++j)
{
if (retArr[0] > arr[j])
{
retArr[0] = arr[j];
AdjustDown(retArr, k, j);
}
}
return retArr;
}解析：
（1）判空k并且开辟返回数组指针
将k值赋给返回大小指针
题目中要求返回数组指针必须是malloc出来的，这里我们采用malloc函数进行开辟
判空如果k==0，那么我们返回NULL或者retArr（是空指针）都可以
*returnSize = k;
int* retArr =(int*)malloc(sizeof(int) * k);
if (k==0)
{
return retArr;
}
（2）将arr中的元素拷贝到retArr中
这里利用for循环将有k个值arr数组进行拷贝
for (int i = 0; i < k; ++i)
{
retArr[i] = arr[i];
}
（3）向下调整retArr为大堆,并且大堆中的元素个数为k个
这里我们采用建大堆而不是小堆是因为：
若采用小堆构建如下图：
第一行是数组，其中k=6，前六个构建一个小堆，如图可知当最小的值1作为堆顶时，最小的k个数的值2比1大无法进入堆中，进而使用小堆进行构建无法进行选出前6个小的元素，故我们采用大堆
采用大堆构建如下图：
显而易见元素作为最小的k个数中的2比堆顶11小那么可以入堆直接覆盖11，调整堆，使用AdjustDown（）函数调整数组保持大堆的性质，使其成为大堆
for (int i = (k-1-1)/2 ; i>=0; --i)
{
//AdjustDown（）字面意思就行
//向下调整一调整就是“侧方垂直”的整个路径
//由于数组的顺序是混乱的没有进行调整，无法保证AdjustDown（）函数两侧都是大堆，那么我们在（k-1-1）/2的位置进行调整。k-1的意思是数组末尾的元素，其作为child结点求其parent结点为（k-1-1）/2，
AdjustDown(retArr, k, i);
}
（4）AdjustDown（）函数的实现
void AdjustDown(int* a,int n,int root)
{
int parent = root;
int child = parent * 2 + 1;
while (child<n)
{
//默认左孩子是大的，将其与右孩子比较，如果小于右节点则换
这里注意当最后一个结点恰好为左节点会存在没有右孩子的情况，这里我们采用child+1<n进行判断
if (child + 1 < n && a[child] < a[child + 1])
{
++child;
}
//parent永远不可能为负数，c语言是取整运算（-1）/2=0，
// 此时parent=child=0，其a[child]=a[parnet]，执行break直接跳出循环，故while循环的条件 //为child<n
if (a[parent] < a[child])
{
//交换
int tmp = a[parent];
a[parent] = a[child];
a[child] = tmp;
//向下进行迭代
//这里即字面意思AdjustDown向下调整，那么就将child的值赋给parent，重新由父结点计 //算出孩子结点，进而达到向下调整迭代的目的
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
（5）比较并且重新赋值然后调整数组成为大堆
令j=k，k为大堆的元素个数同时也为余下数组的第一个数的下标，使j<arrsize进行循环逐渐使最小的k个数进入大堆中去
如果大堆顶retArr[0]大于数组arr[j]那么则直接将arr[j]赋值给retArr[0]中，由于是大堆，那么最小的k个数是一定小于由k个数组成在大堆顶的数，那么其能够进入由k个数组成的大堆（当最小的k个数全部进入大堆中后再也没有数可以进入大堆，因为大堆上的堆顶的数是第k个最小的数，第k+1个小的数>第k个小的数，无法进入大堆），调整数组使其成为大堆
for (int j = k; j < arrSize; ++j)
{
if (retArr[0] > arr[j])
{
retArr[0] = arr[j];
//AdjustDown（）函数由于堆顶两侧都是大堆故是在堆顶进行直接调整
AdjustDown(retArr, k, j);
}
}
（6）返回保存有最小的k个数的retArr数组
return retArr;
到这里我们解题完毕
如果对您有帮助的话点一个免费的赞和收藏叭！
由于作者水平不足，如果有任何错误，麻烦读者评论在评论区指点一下，谢谢！
原文地址：https://blog.csdn.net/2301_80751958/article/details/140573688
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！