赞
踩
在面试中面试官经常会问这样一个问题:现在有N个数,请找出最大的或最小的前k个数,这就是经典的TopK问题,这种问题在实际的业务非常的常见,比如微博的热搜排名,抖音的每日热榜排名等等都是属于这种Top问题。
当我们看到这种题目的时候,大多第一反应都是排序,将这N个数按升序或降序的方式排好序,然后再取前k个最小或最大的数;当然这种思路是没有任何问题的,但问题是选择哪一种排序呢?众所周知,快速排序是排序算法中最时间复杂度相对较优的算法,快速排序的平均时间复杂度是O(N * logN) 。但是本篇将着重使用堆排序进行相应的优化。
堆排序的核心思想:(前提是我们要建好一个相应的堆,这里我们用含N个数的大堆来说) 每次将建好的大堆的最后一个叶子节点和根节点进行互换,然后执行一次向下调整算法调整堆的结构,再将指向堆最后位置的指针减1(相当于将最大的数放在最后一个,并且排除它)。大根堆是所有父亲节点均大于其对应的孩子节点,而我们要求的是升序的堆,大根堆的根节点肯定是堆里最大的数,因此,我们可以通过将根节点和最后一个叶子节点互换,并将最后一个叶子节点的指针减1,即可保存最大的值,但是互换过去的叶子节点破坏了原来大根堆的结构,因此我们就需要用向下调整算法来恢复结构以便于选出次大的数。
堆排序的时间复杂度为O(N * logN)
代码实现
//升序 void HeapSort(int* arr, int n) { //升序要首先建立大堆 //建堆的时间复杂度为o(N) for(int i = ((n - 1) - 1) / 2 ; i >= 0; i--) { AdjustDown(arr,n,i); } //每次选出剩余数中最大的数,并保存到每次最后的节点 int end = n - 1; while(end > 0) { int tmp = arr[end]; arr[end] = arr[0]; arr[0] = tmp; //选出次小的数 //AdjustDown为向下调整算法 AdjustDown(arr,end,0); --end; } }
具体思路分析和相应的算法展示,以及堆排序时间复杂度的计算请看:面试考点–堆(向下调整算法,向上调整算法,建堆,堆排序)以及堆排序、建堆的时间复杂度分析(图文并茂)
当你回答面试官解决此问题可以采用堆排序或快速排序选出前k个数的后,然后面试官可能会提出这样的要求:解决该问题的效率不够,请继续优化。
优化思路:
首先建一个N个数的大堆(小堆),然后每次将根结点(最大的值)移除,然后重新调堆(向下调整算法),继续选出次大的值,然后移除,直至选出k个次大的数;
时间复杂度分析:
向下调整算法的时间复杂度为O(logN),要重新调堆k次,因此时间复杂度为O(K * logN),由于建堆的时间复杂度为O(N),因此该算法的总的时间复杂度为 O(N + K * logN) ,随着n的增大,O(K * logN)会趋于平缓,但 O(N)是线性增长,因此该算法的时间复杂度趋近于O(N)。
当你采用以上回答时,面试官为了更近一步考验你,可能会这样说:假设当N非常大的时候,比如说总共有10亿个数,内存中放不下这么多的数,数据保存在文件中,采用上面的方法会非常耗费内存空间,请继续进行优化。
优化思路:
首先还是先建一个堆,若是求前k个最大的数(降序)就建大堆,反之(升序)建小堆,但此次建堆只建k个数的堆(之前是建N个数的堆),然后将剩下N-K个数依次去和堆顶的数(根节点)进行比较,如果要比堆顶的数大,则替换堆顶的数,再进行向下调整算法,然后循环依次进行比较,最终,最大的前k个数,就在该堆里面;
时间复杂度分析:
首先,建立k个数的堆的时间复杂度为O(K),然后假设在最坏的情况下,需要比较N-K次,也就是说需要进行N-K次向下调整算法,因此,调堆的时间复杂度为O((N-K) * logK);则总的时间复杂度为O(K + (N-K) * logK),由于K是定值,并且现实业务中,往往都是N的值非常的大,然后K的值非常的小,(拿微博热搜来说就是要在全国几亿条新闻中,选出十几或二十几访问量最多的新闻作为热搜),所以,该算法的时间复杂度趋近于O(N)。
代码实现
/* 堆的结构 typedef int HPDataType; typedef struct Heap { HPDataType* _a; int _size; int _capacity; }Heap; */ //找最大的K个元素 //假设堆为小堆 void PrintTopK(int* a, int n, int k) { Heap hp; //建立含有K个元素的堆 HeapInit(&hp, a, k); for (int i = k; i < n; ++i) // N { //每次和堆顶元素比较,大于堆顶元素,则删除堆顶元素,插入新的元素 if (a[i] > HeapTop(&hp)) // LogK { HeapPop(&hp); //在进行插入操作时,会进行调整 HeapPush(&hp, a[i]); } } for(int i = 0; i < k; ++i){ printf("%d ",HeapTop(&hp)); HeapPop(&hp); } }
到此为止,才是最终的既节省内存空间,效率又相对较高的解决TopK问题的解决方案
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。