for(sumCount = 0, v = MAXN -1; v >=0; v--)
cumCount += count[v];
if(sumCount >= k)
break;
return v;
扩展问题:
1.如果需要找出N个数中最大的K个不同的浮点数呢?比如,含有10个浮点数的数组(1.5,1.5,2.5,3.5,3.5,5,0,- 1.5,3.5)中最大的3个不同的浮点数是(5,3.5,2.5)。
解答:除了解法五不行,其他的都可以。因为最后一种需要是正数。
2. 如果是找第k到第m(0<k<=m<=n)大的数呢?
解答:可以用小根堆来先求出m个最大的,然后从中输出k到m个。
3. 在搜索引擎中,网络上的每个网页都有“权威性”权重,如page rank。如果我们需要寻找权重最大的K个网页,而网页的权重会不断地更新,那么算法要如何变动以达到快速更新(incremental update)并及时返回权重最大的K个网页?
解答:(解法三)用堆排序当每一个网页权重更新的时候,更新堆。
举一反三:查找最小的K个元素
解答:最直观的方法是用快速排序或堆排序先排好,在取前K小的数据。最好的办法是利用解法二和解法三的原理进行查找。
目录(?)[-]方法一:常规解法,先排序(时间复杂度为O(N*logN))方法二:利用快速排序原理(时间复杂度O(N*logK)(掌握)方法三:利用最小堆的原理(时间复杂度为O(N*logK))(掌握)方法四:二分法(在实际应用中效果不佳)方法五:用空间换取时间的方法 问题:查找大量无序元素中最大的K个数。
摘要:不同的深度学习库风格各异。那么这些函数库的风格在系统优化和用户体验方面又有哪些优势和缺陷呢?本文旨在于比较它们在编程模式方面的差异,讨论这些模式的基本优劣势,以及可以学到的经验。【编者按】继xgboost,cxxnet,minerva之后,DMLC在9月29日发布了新的Project:dmlc/MXNet,MXNet是cxxnet的进化,在设计上经过成熟的思考,文档也很清楚。尤为难得的是,MXNet开发团队把设计笔记也做了分享。笔记的思想不局限于MXNet,也不局限于深度学习,无论对深度学习初学入门还是对高阶提升,都具有很好的参考价值。本文是第一篇设计笔记的译文,深入讨论了不同深度学习库
遇到题目为从n个无序数组中找出第K大的数,最开始想到的就是冒泡排序、选择排序等,每次找到一个最大(或最小)的,但是很明显需要时间复杂度为O(n*k)!具体代码细节参考findK_2
改进一点的算法有根据快速排序的思想,时间复杂度达到O(n)。想象一下,第k大,说明前面有k-1个元素是比第k个元素大,那么利用快速排序的思想,将大于轴值(暂且固定第一个元素)的放在左边,小于轴值的放在右边...
所谓“第(前)k大数问题”指的是在长度为n(n>=k)的乱序数组中S找出从大到小顺序的第(前)k个数的问题。
注意:题中只需得到最大的K个数,而不需要对后面N-K个数排序
可能存在的条件限制:
要求 时间 和 空间消耗最小、海量数据、待排序的数据可能是...
这是从编程之美中摘选的一个题目,解法十分的快速。详细的可以查看编程之美第二章数字之谜的第11小题。解法是书中的所提出的,但代码是笔者自己上机实现的。如有不完美之处,欢迎大家讨论及指正。
最容易想到的就是循环遍历数组K次求出最大的K个数。
这个算法有许多的缺点:第一点就是速度不够,它的时间复杂度中O(K*N),当数组很大时,不能全部加载到内存中,这个算法就不可行了。
这道题目还有两种比较优的
* 给一个目标数 target, 一个非负整数 k, 一个按照升序排列的数组 A。
* 在A中找与target最接近的k个整数。返回这k个数并按照与target的接近程度从小到大排序,如果接近程度相当,那么小的数排在前面。
* 1. k是一个非负整数,并且总是小于已排序
方法一:使用最小堆。 1、用前k个元素建立一个最小堆;2、遍历无序区域的元素,和堆顶元素对比,如果小于堆顶值,肯定不可能是前k个最大值;如果大于堆顶值,那么取代堆顶元素,做一次堆调整。//最小堆的调整
void heap_adjust_for_maxK(int arr[], int s, int end)
//对堆进行一次调整
//方法:(以大顶堆为例)比较父节点和两个子节点的大小:如果父...