首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入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
135
问题
输入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
"Thecatdoesnotofferservices,"WilliamBurroughswrote."Thecatoffersitself."Butitdoessowithunapologeticcontradict
Writeanessaybasedonthefollowingoutline.Youshouldwriteabout150wordsontheANSWERSHEET.1.教师用课外时间给学生补课赚钱的现象
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如输入整数22和如下二元树10
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:因此返回true。如果输入7、4、6、5,没有哪棵树的后序遍历
将远程服务器中名为“通知”的文件在不下载的情况下进行编辑,修改201教室为303教室,然后直接保存,并在关闭编辑窗口后上传。
请在MSN共享文件会话界面上,利用工具栏添加共享文件,文件位置为“我的文档\注册.txt”。
若按下Shift键同时用鼠标分别单击幻灯片中的标题、文本和图片对象,则()。A.仅最后单击的对象被选中B.三个对象被同时选中C.仅标题对象被选中D.仅图形对象被选中
信息技术的根本目标是()。
IPSAN区别于FCSAN以及IBSAN的主要技术是采用__________实现异地间的数据交换。
随机试题
在我国急性胰腺炎最常见的病因是
在保持流动性及水泥用量不变的条件下使用减水剂,可使混凝土()。
在工程网络计划中,工作的自由时差是指在不影响()的前提下,该工作可以利用的机动时间。
期货价格反映了市场对未来现货价格的预期。()
在下列方法中,能直接用于项目计算期不相同的多个互斥方案比较决策的方法是()。
韦纳认为,学生在对自己的成功和失败进行分析归因时通常会归于()。
一百五十多年来,一些重大发明,如照明、通信、汽车等技术,都是在世博会上面世后才逐渐转化为主流产业的。从文化生活角度看,这是因为()。
下列关于春秋决狱的表述,正确的有()。(2016法多29)
为实现以ADSL方式接入Intemet,至少需要在计算机中内置或外置的一个关键硬设备是()。
ItisknowntousthatEnglishisnotasoldasChinese,butitiswidelyusedbymostpeopleallovertheworld.Englishspeake
最新回复
(
0
)