首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入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
130
问题
输入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
程序员面试
相关试题推荐
"Thecatdoesnotofferservices,"WilliamBurroughswrote."Thecatoffersitself."Butitdoessowithunapologeticcontradict
大概描述一下ASP。NET服务器控件的生命周期
删除字符串中的数字并压缩字符串(神州数码以前笔试题),如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。(下面的算法只需要一次遍历,不需要开辟新空间,时间复杂度为O(N))
公司要求开发一个继承System.Windows.Forms.ListView类的组件,要求达到以下的特殊功能:点击ListView各列列头时,能按照点击列的每行值进行重排视图中的所有行(排序的方式如DataGrid相似)。根据您的知识,请简要谈一下您的
ASP.NET能在那些系统中运行?
存储过程和函数的区别
在桌面上创建一个新浪新闻网页的快捷方式。
在桌面上打开帮助和支持中心,利用“索引”的方法取得关于WindowsXP的“磁盘清理程序”方面的帮助信息。
在“幻灯片浏览视图”模式下,不允许进行的操作是()A.幻灯片移动和复制B.幻灯片切换C.幻灯片删除D.设置动画效果
请利用“外观和主题”窗口,设置屏幕保护为“字幕”,文字为“全国专业技术人员计算机应用能力考试中,请移动鼠标开始”字体为“黑体”,字号为“72”,颜色为“浅绿色”(请按题目的顺序操作)。
随机试题
如图1一41所示,Rab=________Ω。
Mancannotgoonincreasinghisnumberatthepresentrate.Inthe【56】30yearsmanwillfaceaperiodofcrisis.【57】expertsbeli
影响致癌作用的因素有
[2011年,第56题]均质细杆AB重力为P、长2L,A端铰支,B端用绳系住,处于水平位置,如图4.9-18所示。当B端绳突然剪断瞬时AB杆的角加速度大小为()。
在现实市场经济中,导致市场失灵的情况有()。
《中华人民共和国城市规划法》的适用范围包括()。
物业管理企业在制定招聘计划时应考虑哪些因素?
数据库应用系统的设计应该具有数据设计和【】功能,对数据进行收集、存储、加工、抽取和传播等。
把存储在硬盘上的程序传送到指定的内存区域中,这种操作称为()。
Short-termdebtisamajorsourceoffundsforafirm.Forlargefirms,commercialbanksarethesourceofshort-termfinance,a
最新回复
(
0
)