查找最小的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题的数据结构与算法面试题目。这些题目是从微软等知名公司的面试题目中精选出来的,并由原作者进行了整理和发布。以下是对这些题目的详细解读: ### 第...
4. 逻辑关联题:第5题,考查句子之间的逻辑关系。根据语境,B选项“只听见远处传来的几声犬吠”符合独自走在巷子里的寂静氛围。 5. 语病辨析题:第6题,非比喻句是D选项,燕子像黑色的闪电,是比喻句;其他选项都是...
高中联赛难度几何题100道(精华双图版) 本资源包含100道高中联赛难度的几何题,涵盖圆、线、角、点等基本几何元素的性质和关系。本资源可以帮助学生深入理解几何知识,提高解题能力和空间想象力。 知识点: 1. ...
第十四届蓝桥杯EDA赛模拟题一 第十四届蓝桥杯EDA赛模拟题二 第十四届蓝桥杯EDA省赛真题 第十五届蓝桥杯EDA赛模拟试题一(嘉立创EDA提供) 第十五届蓝桥杯EDA赛模拟试题二(嘉立创EDA提供) 4T十五届模拟三
南开100题是针对计算机三级网络技术机试的一个复习资料集,它包含了过去考试中出现过的实际题目。这些题目旨在帮助考生熟悉考试内容和题型,提高备考效率。 ### 2. 题目分类 题目分为两大类:带有特殊标记的题目...
9. **应用题解法**:五部分的解答题,如1题、3题、4题、5题、6题,要求将数学知识应用于实际问题,如人数比例、卖出与剩余的比、速度比、混凝土配比、水费分摊等。 10. **判断题的逻辑**:五部分的判断题,不仅考察...
5. "江河日下"形容事物逐渐衰落,第五题中误用,应理解为环境恶化。 6. "炙手可热"形容权势显赫,第六题中用于"规范化"讨论,用词不妥。 7. "博闻强志"意指见闻广博,记忆力强,第七题中用来形容优秀学生恰当。 8. ...
背题当然就是背前面说的南开100题啦,其实虽然号称100题,也不过10多个题型而已,这个在我提供的下载地址里已经分好类别了。把这些题型背下来就可以了;网络上有精简版以及笔者的背诵版可供参考。背诵要在理解的基础...
3. 应用题:第3题、第5题等,涉及实际生活场景,提高孩子解决实际问题的能力。 4. 数列与规律:第9题、第13题、第14题,要求找出数字间的规律,训练孩子的观察力和逻辑思维。 5. 符号操作:第10题,通过在数字间添加...
"小学一年级数学下册第五单元综合练习题2套精选" 本资源是小学一年级数学下册第五单元的综合练习题,涵盖了人民币的基本知识和应用,旨在帮助学生巩固和扩展对人民币的理解。 一、填充数值 在人民币的计算中,...
5. 应用加法解决问题:第五题是关于书的页数,通过已知已读和未读页数求总页数,78 + 22 = 100。 6. 减法解决问题:第六题妈妈购物后的剩余金额,83 - 28 = 55。 7. 差值计算:第七题书架上拿走书的数量,36 - 9 =...
2. **比较和排序**:如第5题和第10题,孩子们需要比较不同个体的数量,以确定谁多谁少。 3. **序列和位置**:第3题和第5题考察了孩子对序列和位置的理解,比如"小明前面有4个人,后面有4个人"这样的表述。 4. **...