首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入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
134
问题
输入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
程序员面试
相关试题推荐
TruthinadvertisingisaconceptcentraltotheAmericanfreemarketeconomicsystem.Accordingtothistheory,companiesthat
ForAmerica’schildrentheeducationsystemisoftenliterallyalottery.ThatisthemainmessageofanewdocumentaryaboutAm
列举ADO.NET中的五个主要对象,并简单描述
输入两个整数序列。其中一个序列表示栈的push顺序,判断另一个序列有没有可能是对应的pop顺序。为了简单起见,我们假设push序列的任意两个整数都是不相等的。比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。因
什么是ASP.net中的用户控件
Dreamweaver的视图(View)菜单中,Grid→settings表示______。A.选择计量系统来设定标尺单位B.显示一个应用当前设置的背景网格C.使插入对象与最近的对齐设置对齐D.进行网格设置
在PPoint中,被选中对象虚框上的8个小方框称为()。A.尺寸控制点B.文本插入点C.有效区域范围D.选中对象标记
请对工作簿Book1的结构和窗口设置保护,使工作簿和工作表不能进行移动和隐藏等操作。
下列不属于软件调试技术的是()。
RIPv1与RIPv2的区别是()。
随机试题
从重从快惩处严重刑事犯罪分子的前提是()。
从东南亚入境一男子,3天前因突然剧烈呕吐,腹泻而入院,腹泻呈米泔水样,便检发现穿梭状运动的细菌,请问致病菌可能是()
∫ex(cosex)dx
下列关于大鼠抓法的叙述,错误的是
案情:2012年11月,甲因为严重肠炎到乙医院进行手术,手术很顺利,伤口也愈合得很快。但出院后,却时常感觉到腹内疼痛。2013年6月,经另外一家医院诊治,其腹腔内尚留有手术用的纱布。甲认为,从2012年11月至今,自己未在任何医院进行过手术。所以这块手术纱
以下关于物权保护采取方式的表述错误的是()。
用友报表系统中,数值单元的内容只能通过计算公式生成。()
()科目编码必须按财政部的统一编码方案进行编制。
为了保证数据库系统稳定运行,需要使用服务器容错技术保证其运行服务器的可靠性。下列有关Active-Standby模式服务器容错技术的说法,错误的是()。
Whattimeistheman’sflight?Whatisthereductioninthecompany’sexports?
最新回复
(
0
)