首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入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
2019-03-29
136
问题
输入n个整数,输出其中最小的k个。
例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。
选项
答案
#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); } } } }
解析
这道题最简单的思路莫过于把输入的n个整数排序,这样排在最前面的k个数就是最小的k个数。只是这种思路的时间复杂度为O(nlogn)。我们试着寻找更快的解决思路。
我们可以开辟一个长度为k的数组。每次从输入的n个整数中读入一个数。如果数组中已经插入的元素少于k个,则将读入的整数直接放到数组中。否则长度为k的数组已经满了,不能再往数组里插入元素,只能替换了。如果读入的这个整数比数组中已有k个整数的最大值要小,则用读入的这个整数替换这个最大值;如果读入的整数比数组中已有k个整数的最大值还要大,则读入的这个整数不可能是最小的k个整数之一,抛弃这个整数。这种思路相当于只要排序k个整数,因此时间复杂可以降到O(n+nlogk)。通常情况下k要远小于n,所以这种办法要优于前面的思路。
这是我能够想出来的最快的解决方案。不过从给面试官留下更好印象的角度出发,我们可以进一步把代码写得更漂亮一些。从上面的分析,当长度为k的数组已经满了之后,如果需要替换,每次替换的都是数组中的最大值。在常用的数据结构中,能够在O(1)时间里得到最大值的数据结构为最大堆。因此我们可以用堆(heap)来代替数组。
另外,自己重头开始写一个最大堆需要一定量的代码。我们现在不需要重新去发明车轮,因为前人早就发明出来了。同样,STL中的set和multiset为我们做了很好的堆的实现,我们可以拿过来用。既偷了懒,又给面试官留下熟悉STL的好印象,何乐而不为之?
转载请注明原文地址:https://kaotiyun.com/show/6xmZ777K
0
程序员面试
相关试题推荐
______isthecenterofourplanetarysystemwasadifficultconcepttograspintheMiddleAges.
TheUnitedStatesInterstateHighwaySystemisaninfrastructurefeatofunprecedentedproportions.Notonlydoesitjoinallfi
编码实现字符串转整型的函数(实现函数atoi的功能),据说是神州数码笔试题。如将字符串”+123”-->123,”-0123”-->-123,“123CS45”-->123,“123.45CS”-->123,“CS123.45”-->0
2005年11月金山笔试题。编码完成下面的处理函数。函数将字符串中的字符’*’移到串的前部分,前面的非’*’字符后移,但不能改变非’*’字符的先后顺序,函数返回串中字符’*’的数量。如原始串为:ab**cd**e*12,处理后为*****abcde12,函
输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。例如输入12,从1到12这些整数中包含1的数字有1,10,11和12,1一共出现了5次。
概述.NET里对remoting和webservice两项技术的理解和实际中的应用。
启动操作系统自带的Intemet连接防火墙。
在“幻灯片浏览视图”模式下,不允许进行的操作是()A.幻灯片移动和复制B.幻灯片切换C.幻灯片删除D.设置动画效果
当密码为123456时,请撤消对工作簿Book1的密码及结构保护设置。
论IT服务规划设计IT服务规划设计处于IT服务生命周期的前期,如果前期未进行有效的规划设计,那么仓促而就的IT服务就难以满足客户的真正需求,可能造成IT服务可用性降低、客户满意度低下等问题。为确保有效做好IT服务规划设计,服务供方在IT服务规划设计过程中
随机试题
A.疏肝消积,顺气化痰B.降逆平喘、止咳化痰C.和胃理气,降逆止呕D.培肾固本,温补下元E.健脾和胃,消食和中
【背景资料】某新建办公楼工程,总建筑面积18600m2,地下2层,地上4层,层高4.5m,筏板基础,钢筋混凝土框架结构。在施工过程中。发生了下列事件:事件1:工程开工前,施工单位按规定向项目监理机构报审施工组织设计,监理工程师审核时,发现“施工进度计
目前我国在()时有零数委托。
维修性设计中的简化设计的基本原则不包括()。
我国东南沿海某市原为农产品和部分轻工业原料生产基地,1990年开始积极吸引外资,调整产业结构,建立起以化工、机械、纺织、电子、服装等为主的工业体系。下图是该市1990—2010年产业结构变化图。读图回答以下题。1990—2010年,该市产业结构变化的
【2015.河南新乡】教师要做到“不讽刺,挖苦,歧视,体罚学生”体现了教师职业道德规范中的()。
深蓝色的天空里悬着无数_____________的星。船在动,星也在动,它们是这样低,真是_____________呢!渐渐地我的眼睛模糊了,我好像看见无数萤火虫在我的周围飞舞。海上的夜是柔和的,是静寂的,是_____________的。填入画横线部分最
人生观的核心是
已知函数f(x)满足则f(x)=__________.
在下面所列的几种关系中,不可以作为关系型数据库的关系的是()。
最新回复
(
0
)