首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入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
98
问题
输入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
程序员面试
相关试题推荐
______isthecenterofourplanetarysystemwasadifficultconcepttograspintheMiddleAges.
Theimmunesystemisequalincomplexitytothecombinedintricaciesofthebrainandnervoussystem.Thesuccessoftheimmune
ForAmerica’schildrentheeducationsystemisoftenliterallyalottery.ThatisthemainmessageofanewdocumentaryaboutAm
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
Remoting简介
大整数数相乘的问题。
ASP.NET能在那些系统中运行?
执行下面代码后:
将金山网镖应用程序规则列表中的应用程序QQ2009删除。
Dreamweaver的视图(View)菜单中,Grid→settings表示______。A.选择计量系统来设定标尺单位B.显示一个应用当前设置的背景网格C.使插入对象与最近的对齐设置对齐D.进行网格设置
随机试题
A、learnB、heartC、earthD、heardB
健康危险度评价的主要特点是
有关冠状面的叙述,错误的是
生产性毒物进入人体最重要的途径是
患者,男性,78岁,慢性肺源性心脏病10年,2天前于受凉后咳嗽、咳痰、呼吸困难,加重伴少尿、双下肢水肿。1天前出现失眠、间断烦躁不安急诊入院。查体:体温37.8℃,呼吸困难,烦躁不安,口唇发绀,呼吸24次/分,双肺散在湿哕音及哮鸣音,心率.126次/分,心
某土石坝面碾压施工设计碾压遍数为5遍,碾滚净宽为4m,则错距宽度为()m。
母牛:牲畜
正因为中国法律史学除了单纯的理论研究,还要探究解决当代中国的法律问题,所以有必要坚持独立的中国立场,不论是单纯的理论研究,还是切近实际的应用研究,都需坚持独立思想立场,才能做出有价值的研究成果。这里的独立立场,其实就是中国自身的立场,而不是站在别国的立场之
中国国家主席习近平在人民大会堂会见21世纪理事会北京会议外方代表时表示,我们对中国经济保持持续健康发展抱有信心,中国不会落人所谓中等收入国家陷阱。一个国家落入“中等收入陷阱”的表现不包括()。
考生文件夹下存在一个数据库文件“samp3.accdb”,里面已经设计了表对象“tEmp”、窗体对象“fEmp”、报表对象“rEmp”和宏对象“mEmp”。同时,给出窗体对象“fEmp”的若干事件代码,试按以下功能要求补充设计。功能:窗体加载事件实现的
最新回复
(
0
)