首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入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
115
问题
输入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
程序员面试
相关试题推荐
[A]Theperson-skillsmatchapproachtoselection[B]Theimpactsofbadselectiondecisions[C]Theimportanceofstructu
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1,-2,3,10,-4,7,2,-5,和最大的子数组为3,10,
C#中要使一个类支持FOREACH遍历,实现过程怎样?
公司要求开发一个继承System.Windows.Forms.ListView类的组件,要求达到以下的特殊功能:点击ListView各列列头时,能按照点击列的每行值进行重排视图中的所有行(排序的方式如DataGrid相似)。根据您的知识,请简要谈一下您的
在桌面上创建一个新浪新闻网页的快捷方式。
添加一个新的类型是计算机管理员的用户John
在PPoint中,对于艺术字的用法,以下说法不正确的是()。A.艺术字是作为文本对象处理的B.艺术字是作为图形对象处理的C.艺术字有多种式样和字体字号D.艺术字可整体缩放
以下关于输入法状态切换的组合键正确的是______A.使用Ctrl+、来切换中文标点和英文标点B.使用Ctrl+空格键来打开或关闭中文输入法C.使用Shift+空格键来切换半角输入模式和全角输入模式D.使用Shift+Ctrl来切换半角输入模式和
椭圆曲线密码ECC是一种公开密钥加密算法体制,其密码由六元组T=<p,a,b,G,n,h>表示。用户的私钥d的取值为1._____,公钥Q的取值为2.______。利用ECC实现数字签名与利用RSA实现数字签名的主要区别是3.____
RIPv1与RIPv2的区别是()。
随机试题
法国存在主义运动的奠基之作是()
TheNorwegianNobelCommitteehasdecidedto【21】theNobelPeacePrizefor1998toJohnHumeandDavidTrimblefortheirefforts
妊高症患者发生抽搐时,首要的护理措施是
中国甲公司(买方)与日本乙公司(卖方)签订了一份货物买卖合同。双方在合同中约定将履行合同过程中的一切争议提交给设在中国的某仲裁委员会仲裁。后双方发生了纠纷,中国甲公司声称货物质量不合格,向该仲裁委员会申请仲裁。经审理,仲裁庭裁决驳回中国公司的请求,同时裁决
城镇职工基本医疗保险的覆盖范围包括()。
公文的作者是指()。
一个人真正的“精神饥饿感”应该从中小学时期开始培养。现阶段我国必须在学校教育阶段“拯救阅读”,尤其是儿童阅读。“‘阅读是消灭无知、消灭贫穷、消灭绝望的武器’。一个民族精神境界的高下取决于阅读的水平;一个人的阅读史,就是他的精神发育史;一个没有阅读的学校永远
如今,美国的科学家能用机器或科学验证武林传说的真假。首先接受检验的是拳法。研究人员使用的装置是三号混合拟人试验装置——也就是我们所熟知的试车假人。试车假人经过政府认证,可精确模拟人体,并测量人体承受的伤害。假人中的感应器可以测量每一拳的力量和杀伤力。测试显
张丽要么向公司请假并在一年以后回公司,要么辞去她现在的工作,除非她收到了某个名牌大学的为期一年的奖学金,否则她不会这样做。如果公司没有发现她收到奖学金的话,那么将准许她请假,否则将不给予批准。因此,张丽不会辞去公司的工作,除非公司发现她收到了奖学金。上述论
WhyDepressionNeedsaNewDefinition[A]Manypsychiatristsbelievethatanewapproachtodiagnosingandtreatingdepression—li
最新回复
(
0
)