查找最小的k个元素(数组)
题目:输入n个整数,输出其中最小的k个。
例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。
一,最原始的一种方法
插入排序,后输出最小的k个
源码:
缺点:时间复杂度高。O(n^2);
二,简单优化后
排序方法使用快速排序
分析:虽然时间提高了,但是还是可以再优化。O(nlogn)
三,再次优化
维护一个K大小的数组,只用遍历一次n个元素,然后就能得到最小的k个元素。
伪代码:
1, 将n个元素前k个放入数组中,每插入一个元素,对k数组中元素进行插入排序;
2,从第k+1开始,每遍历一个元素,跟数组中最大的(maxK)比较 maxK>a则将maxK删除,将a插入k中。直到程序结尾。
源码:
五,还能优化,将维护一个k大小数组换成维护一个k大小堆
六,最后四种方法综合代码如下
分享到:
相关推荐
03第五章第五章P60-P85.rar 04第六章第章第八章P85-P8113.ram 05第九章第十章p114-P137.rar 06第十章第章P138-P165.rar 07第十■章第十■章D165-P185.ram 08第十三章第十四章p186-P218.rar 09第十四章第十五章P219-P...
5.[最新答案V0.3版]微软等数据结构+算法面试100题[第21-40题答案] http://download.csdn.net/source/28328626 [答案V0.2版]精选微软数据结构+算法面试100题[前20题]--修正 http://download.csdn.net/source/2813890 ...
03 第五章 第五章P60-P85 04 第六章 第七章第八章P85-P8113 05 第九章 第十章P114-P137 06 第十一章 第十二章P138-P165 07 第十二章 第十二章P165-P185 08 第十三章 第十四章P186-P218 09 第十四章 第十五章P219-P...
6. **颜色合并**:第5题中,异色相加为黑,同色相加为白,考察颜色的组合规则。 7. **线条计算**:第6题要求计算图形的笔画数,包括重叠线条,考察空间思维和细节观察。 8. **阴影组合**:第7题的阴影部分可以组成...
"电路"邱关源第五版课后习题答案pdf 本资源为《电路》邱关源第五版课后习题答案pdf,包含了电路模型和电路定律、电阻电路的等效变换、电阻电路的一般分析方法等部分的习题答案和解析。 电路模型和电路定律 在...
第5题 函数fun的功能是将大于整数m且紧靠m的k各素数存入xx所指的数组中。知识点: * 循环语句的使用 * 条件语句的使用 * 数组的使用 * 素数的判断 第6题 函数fun的功能是删除以各字符串中指定下标的字符。知识点:...
根据提供的信息,我们可以总结出这份文档包含了从第41题到第60题的数据结构与算法面试题目。这些题目是从微软等知名公司的面试题目中精选出来的,并由原作者进行了整理和发布。以下是对这些题目的详细解读: ### 第...
高中联赛难度几何题100道(精华双图版) 本资源包含100道高中联赛难度的几何题,涵盖圆、线、角、点等基本几何元素的性质和关系。本资源可以帮助学生深入理解几何知识,提高解题能力和空间想象力。 知识点: 1. ...
5. **第五题**:题目要求找到大于给定整数`m`且紧邻的`k`个素数。这涉及到素数检测(通常通过试除法实现)和数组填充。在C语言中,可以通过循环和条件判断来实现素数检测,同时利用数组来存储找到的素数。 6. **第...
第五题中,证明了KG垂直于BG,这一过程中用到了圆内接四边形的性质以及角度的对称性。这说明了在圆中处理角度和线段关系的能力是解决此类问题的关键。 第六题中,通过切线与圆的关系,证明了E为BF中点。这需要理解...
第十四届蓝桥杯EDA赛模拟题一 第十四届蓝桥杯EDA赛模拟题二 第十四届蓝桥杯EDA省赛真题 第十五届蓝桥杯EDA赛模拟试题一(嘉立创EDA提供) 第十五届蓝桥杯EDA赛模拟试题二(嘉立创EDA提供) 4T十五届模拟三
南开100题是针对计算机三级网络技术机试的一个复习资料集,它包含了过去考试中出现过的实际题目。这些题目旨在帮助考生熟悉考试内容和题型,提高备考效率。 ### 2. 题目分类 题目分为两大类:带有特殊标记的题目...
9. **应用题解法**:五部分的解答题,如1题、3题、4题、5题、6题,要求将数学知识应用于实际问题,如人数比例、卖出与剩余的比、速度比、混凝土配比、水费分摊等。 10. **判断题的逻辑**:五部分的判断题,不仅考察...
python 面试宝典 100 题 本资源为 python 面试宝典,共收录 100 道题目,涵盖了 python 语言的多个方面,从基础知识到高级应用,覆盖了 python 开发者在实际工作中常见的问题和挑战。本资源适合 python 开发者、...
5. "江河日下"形容事物逐渐衰落,第五题中误用,应理解为环境恶化。 6. "炙手可热"形容权势显赫,第六题中用于"规范化"讨论,用词不妥。 7. "博闻强志"意指见闻广博,记忆力强,第七题中用来形容优秀学生恰当。 8. ...
背题当然就是背前面说的南开100题啦,其实虽然号称100题,也不过10多个题型而已,这个在我提供的下载地址里已经分好类别了。把这些题型背下来就可以了;网络上有精简版以及笔者的背诵版可供参考。背诵要在理解的基础...
3. 第三题是基于排名和比较的,要求计算小猪需要超过多少只小动物才能和小兔并列第5。 4. 第四题考察的是四位数的性质,寻找数字和为34的四位数。 5. 第五题是一个逐步减少的序列问题,通过逆向计算找出初始数量。 6...
3. 应用题:第3题、第5题等,涉及实际生活场景,提高孩子解决实际问题的能力。 4. 数列与规律:第9题、第13题、第14题,要求找出数字间的规律,训练孩子的观察力和逻辑思维。 5. 符号操作:第10题,通过在数字间添加...