首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入n个整数,输出其中最小的k个。 例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。
输入n个整数,输出其中最小的k个。 例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。
admin
2014-11-15
119
问题
输入n个整数,输出其中最小的k个。
例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。
选项
答案
我们可以开辟一个长度为k的数组。每次从输入的n个整数中读入一个数。如果数组中已经插入的元素少于k个,则将读入的整数直接放到数组中。否则长度为k的数组已经满了,不能再往数组里插入元素,只能替换了。如果读入的这个整数比数组中已有k个整数的最大值要小,则用读入的这个整数替换这个最大值;如果读入的整数比数组中已有k个整数的最大值还要大,则读入的这个整数不可能是最小的k个整数之一,抛弃这个整数。这种思路相当于只要排序k个整数,因此时间复杂可以降到O(n+nlogk)。通常情况下k要远小于n,所以这种办法要优于前面的思路。 这是我能够想出来的最快的解决方案。不过从给面试官留下更好印象的角度出发,我们可以进一步把代码写得更漂亮一些。从上面的分析,当长度为k的数组已经满了之后,如果需要替换,每次替换的都是数组中的最大值。在常用的数据结构中,能够在O(1)时间里得到最大值的数据结构为最大堆。因此我们可以用堆(heap)来代替数组。 另外,自己重头开始写一个最大堆需要一定量的代码。我们现在不需要重新去发明车轮,因为前人早就发明出来了。同样,STL中的set和multiset为我们做了很好的堆的实现,我们可以拿过来用。既偷了懒,又给面试官留下熟悉STL的好印象,何乐而不为之? 参考代码: #include
#include
#include
using namespace std; typedef multiset
> IntHeap; /////////////////////////////////////////////////////////////////////// // find k least numbers in a vector /////////////////////////////////////////////////////////////////////// void FindKLeastNumbers ( const vector
& data, // a vector of data IntHeap& leastNumbers, // k least numbers, output unsigned int k ) { leastNumbers.clear(); if(k == 0 || data.size() < k) return; vector
::const_iterator iter = data.begin(); for(; iter != data.end(); ++ iter) { // if less than k numbers was inserted into leastNumbers if((leastNumbers.size()) < k) leastNumbers.insert(*iter); // leastNumbers contains k numbers and it’s full now else { // first number in leastNumbers is the greatest one IntHeap::iterator iterFirst = leastNumbers.begin(); // if is less than the previous greatest number if(*iter < *(leastNumbers.begin())) { // replace the previous greatest number leastNumbers.erase(iterFirst); leastNumbers.insert(*iter); } } } }
解析
转载请注明原文地址:https://kaotiyun.com/show/ExmZ777K
0
程序员面试
相关试题推荐
ForAmerica’schildrentheeducationsystemisoftenliterallyalottery.ThatisthemainmessageofanewdocumentaryaboutAm
TheUnitedStatesInterstateHighwaySystemisaninfrastructurefeatofunprecedentedproportions.Notonlydoesitjoinallfi
判断单链表中是否存在环(网上说的笔试题)
公司要求开发一个继承System.Windows.Forms.ListView类的组件,要求达到以下的特殊功能:点击ListView各列列头时,能按照点击列的每行值进行重排视图中的所有行(排序的方式如DataGrid相似)。根据您的知识,请简要谈一下您的
什么是ASP.net中的用户控件
从“系统属性”出发安装网卡驱动程序。
从当前界面开始,到“电话和调制解调器的选项”中,将系统中的标准56000bps调制解调器删除。
不能显示和编辑备注内容的视图模式是()A.普通视图B.大纲视图C.幻灯片视图D.备注页视图
对于PPoint中的视图模式,以下说法错误的是()。A.幻灯片浏览视图下不能设置放映方式B.幻灯片视图注重于对幻灯片的文本和对象进行详细操作C.每种视图模式在演示文稿的制作和显示中有不同的作用D.大纲视图便于查看和编排演示文稿的大纲
在foxpro中定义数据库结构时,字段名的宽度最多可以是()。A.2B.4C.10D.16
随机试题
某投资人准备投资于A公司的股票,A公司没有发放优先股,2009年的有关数据如下:每股净资产为10元,每股盈余为1元,每股股利为0.4元,该公司预计未来不增发股票,并且保持经营效率和财务政策不变,现行A股票市价为15元,目前国库券利率为4%,证券市场平均收益
非特异性感染的典型症状是
咬肌间隙感染如未及时切开引流,最常引起的并发症是
患者头晕眼花,心悸多梦,手足麻,唇甲色淡,经诊断为血虚,补血药处方中,配以益气药物其依据是()。
对于患有职业病的职工变动工作后,当这个职工到新单位后,其职业病待遇应由()承担。
中国古代的科学著作大多是经验型的总结,而不是理论型的探讨,所记各项发明都是为了解决国家与社会生活中实际问题,而不是试图在某一研究领域获得重大突破。从研究方法上来说,中国科技重视综合性的整体研究,重视从总体上把握事物,而不是把研究对象从错综复杂的联系中分离出
如下图所示,梯形下底是上底的1.5倍,梯形中阴影面积等于空白面积,三角形OBC的面积是12,那么三角形AOD的面积是()。
关于疫苗,下列说法错误的是()。
在80x86微处理器系统中,从下列哪一种微处理器开始已经将浮点运算部件集成到CPU芯片内部?
ChristmasCandlesFranklyspeaking,Christmascandlesarenodifferent/fromanyotherdecorativecandle/thatyoumightf
最新回复
(
0
)