当前位置：首页 > news >正文

面试题 17.14.最小K个数

news 来源：原创 2024/9/20 11:34:35

题目：如下图

答案：如下图

/*** 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]，执行breakif (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);
}
}