首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入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
114
问题
输入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
程序员面试
相关试题推荐
AnE-mailtoaRoommate写给室友的邮件YouaregoingtostudyabroadandshareanapartmentwithJohn,alocalstudent.Writehimane-
"Thecatdoesnotofferservices,"WilliamBurroughswrote."Thecatoffersitself."Butitdoessowithunapologeticcontradict
[A]Updateyourbudget[B]Submitachangeofaddressform[C]Bookacleaningservicebeforehand[D]Scheduleawalk-t
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
2005年11月金山笔试题。编码完成下面的处理函数。函数将字符串中的字符’*’移到串的前部分,前面的非’*’字符后移,但不能改变非’*’字符的先后顺序,函数返回串中字符’*’的数量。如原始串为:ab**cd**e*12,处理后为*****abcde12,函
在金山网镖中添加一个端口过滤规则,其中端口为3080,协议为TCP,类型为远程,操作为禁止。
在写字板文件中插入一个Word文档对象,内容为"祝你取得成功!"。保存在C盘下。
在幻灯片播放过程中,单击一次鼠标左键会()。A.切换到第一张幻灯片B.切换到最后一张幻灯片C.切换到上一张幻灯片D.切换到下一张幻灯片或本张幻灯片的下一个播放对象
论IT服务监督管理监督管理是依据国家IT服务标准对IT服务进行整体评价,并对供方的服务过程、交付结果实施监督和绩效评估。在监督管理环节,需要采取适当的方法,对IT服务全生命周期各个阶段的过程和质量进行度量与评价,并对服务供方的服务过程、交付结果实施监理,
随机试题
Ham试验通常用于何种疾病的诊断
患者,男,41岁。血清学诊断结果显示人巨细胞(HCMV)IgG抗体阳性,关于该病毒的叙述,错误的是
为使夏季室内少开空调,应该首先抑制:(2005,44)
水泥砂浆楼地面,按设计图示尺寸以面积计算,应扣除()。
燃烧产物中的烟尘(炭黑)是指由烟中落下来的大直径炭黑粒子。悬浮于大气中能被人们看到的烟一般是直径在()的极小的炭黑粒子。
下列关于农业的说法错误的是()。
一个生态系统由四个基本部分构成,即生产者、消费者、分解者和非生物环境。____________指绿色植物和某些能进行光合作用和化能作用的细菌。它们在生态系统中占据着重要的基础地位。______________指直接和间接以生产者为食物的各种动物,如食肉动物
设随机变量X和Y都服从正态分布,则()
[*]
如果能______平均率看一看人们的忧虑,就会发现,他们忧虑的事,十分之九都不会成为事实。
最新回复
(
0
)