面试题 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;

到这里我们解题完毕

如果对您有帮助的话点一个免费的赞和收藏叭!

由于作者水平不足,如果有任何错误,麻烦读者评论在评论区指点一下,谢谢!

相关推荐

  1. 剑指offer--k个数

    2024-07-22 04:08:01       34 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-22 04:08:01       104 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-22 04:08:01       115 阅读
  3. 在Django里面运行非项目文件

    2024-07-22 04:08:01       94 阅读
  4. Python语言-面向对象

    2024-07-22 04:08:01       100 阅读

热门阅读

  1. 周六算法加练

    2024-07-22 04:08:01       26 阅读
  2. qt 数字转字符

    2024-07-22 04:08:01       26 阅读
  3. qt log 输出为文件

    2024-07-22 04:08:01       24 阅读
  4. 谈谈如何快速学习一门技术

    2024-07-22 04:08:01       24 阅读
  5. WebGIS面试题(第八期)

    2024-07-22 04:08:01       21 阅读
  6. 算法的概述

    2024-07-22 04:08:01       22 阅读
  7. 2024年水利水电安全员考试题库及答案

    2024-07-22 04:08:01       25 阅读
  8. c语言(7.21)

    2024-07-22 04:08:01       23 阅读
  9. 原型继承和原型链

    2024-07-22 04:08:01       25 阅读
  10. 【渗透入门】反序列化

    2024-07-22 04:08:01       23 阅读
  11. Windows图形界面(GUI)-DLG-C/C++ - 月历控件(MonthCalendar)

    2024-07-22 04:08:01       25 阅读
  12. Dijkstra

    2024-07-22 04:08:01       24 阅读