首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
牛客1481368号
2016-09-08 16:44
已编辑
东北大学 C++
关注
已关注
取消关注
n个数值选出最大m个数(3<m<n)的最小算法复杂度是多少?
为什么不可以先建一个大小为n的大顶堆,然后从调整m次堆,复杂度就是就m*logn吗?
leetcode上的解法是建一个m大小的小顶堆,调整n词,复杂度是n*logm
到底哪个更优啊
提示
全部评论
推荐
最新
楼层
牛客399835号
还不错的学校 Java
用快速选择算法平均时间复杂度为O(n),还可以用Median of medians,也叫BRPRT算法可以保证是O(n)的
点赞
回复
分享
发布于 2016-09-08 16:50
heda
清华大学 算法工程师
部分快排 时间复杂度 O(N) 存储复杂度 O(N) 堆排序 时间复杂度 O(NlogM) 空间复杂度 O(M) 这题没啥好说的,也没有正确答案,答出第一个,面试官会问你如果内存存不下整个数组怎么办,答出第二个,面试官会问你有没有更快的。都被问到好几次了
1
回复
分享
发布于 2016-09-09 09:50
--海-星--
快手_软件开发工程师
最小复杂度 O(N) 快排思想
点赞
回复
分享
发布于 2016-09-08 19:51
你好,天朝
中国科学院大学 C++
当N足够大时,建大小为n的方法优
点赞
回复
分享
发布于 2016-09-08 20:06
./a.out
安徽大学 C++
支持一楼的,BFPRT算法可以保证O(N)的复杂度,在O(N)的复杂度先选出第K大的数,之后再遍历一遍选出比第K大的数小的数,复杂度还是O(N)
点赞
回复
分享
发布于 2016-09-08 22:30
牛客1481368号
楼主
东北大学 C++
牛客网上给的答案是nlogm O(n)答案不对 按照楼上的意思是O(mn)
点赞
回复
分享
发布于 2016-09-09 08:34
一只补习的Fyu
左家垅男子职业技术学院 C工程师
建小顶堆,你求M个最大的,保证堆顶是M个中最小的,复杂度是O(nlogm),你不可能比n小,怎么也得遍历一遍吧。
点赞
回复
分享
发布于 2016-09-09 13:25
还没有回复哦~
相关推荐
11-23 10:48
门头沟学院 Java
秋招0offer,感觉心气被磨没了
忙碌了两三个月,收获的只有几个烂意向,全部拒了,到头来还是一场空,怀疑自己读研的意义现在的心态有点像三和大神,感觉事情都是没有意义的,提不起劲,刚入学时意气风发的少年去哪了
Hanak01_offer多多版:
+1
点赞
评论
收藏
分享
昨天 11:29
小红书_社区技术部_前端开发(实习员工)
10.30字节一面
【再再再再再再再战字节,摆烂了,这次一面都没过(手撕做出来了前面还有几轮字节面试忘记录音了,就不记录了。1.自我介绍2.主要技术栈是3.是否了解react4.做题【建议下次做这种题目拿个草稿纸!!】 console.log('start'); setTimeout(() => { console.log('children2'); setTimeout(function() { console.log('children8'); }, 0) ; Promise.resolve().then(() => { console.log('chil...
查看16道真题和解析
面经烤面筋
点赞
评论
收藏
分享
11-18 10:36
内蒙古民族大学 Java
二本实习简历,初筛都过不去
狠狠的赚一笔😋
听说改名字就能收到offer哈:
Radis写错了兄弟
点赞
评论
收藏
分享
11-07 10:30
门头沟学院 前端工程师
终于轮到我了
lastday 知无不言
无敌虾孝子:
喜欢爸爸还是喜欢妈妈
点赞
评论
收藏
分享
11-26 01:07
香港大学 Java
小米终于补发offer了!
但现在面临选择:是留在这里,还是去北京的测开岗位?这真是人生的十字路口,让我很纠结。虽然小米的机会很诱人,但我也不想轻易放弃现在的工作。希望能找到一个明智的决定,真心希望大家能给我一些建议!
投递小米集团等公司10个岗位 >
牛客创作赏金赛
点赞
评论
收藏
分享
点赞成功,聊一聊 >
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
从露宿街头到百万级种子轮融资——我的大学时代经历了什么
3.2W
2
...
C++选手秋招总结
1.5W
3
...
字节20多面终究一场空
1.3W
4
...
华为电话oc了
8543
5
...
泡出来啦
8303
6
...
寒假实习租房攻略!北京版
7924
7
...
阿里云管培生开奖了
7545
8
...
不装了!牛客就是OFFER判官
6684
9
...
放弃代码,结束秋招啦!
6401
10
...
秋招圆满结束
6045
正在热议
#
25届秋招总结
#
355086次浏览
3470人参与
#
我的实习求职记录
#
6087549次浏览
83707人参与
#
阿里云管培生offer
#
42329次浏览
963人参与
#
地方国企笔面经互助
#
5283次浏览
13人参与
#
职场吐槽大会
#
90816次浏览
752人参与
#
选完offer后,你后悔学本专业吗
#
23076次浏览
165人参与
#
北方华创开奖
#
50248次浏览
451人参与
#
ai智能作图
#
4048次浏览
77人参与
#
运营商笔面经互助
#
92830次浏览
1335人参与
#
实习中的菜狗时刻
#
278952次浏览
2741人参与
#
腾讯求职进展汇总
#
200434次浏览
1665人参与
#
如果有时光机,你最想去到哪个年纪?
#
25009次浏览
513人参与
#
当下环境,你会继续卷互联网,还是看其他行业机会
#
37806次浏览
345人参与
#
风评不好的公司,你会去吗?
#
20757次浏览
94人参与
#
上班苦还是上学苦呢?
#
91428次浏览
795人参与
#
大疆求职进展汇总
#
413787次浏览
2934人参与
#
国企还是互联网,你怎么选?
#
90216次浏览
703人参与
#
硬件兄弟们 甩出你的华为奖状
#
73821次浏览
609人参与
#
远程面试的尴尬瞬间
#
20567次浏览
296人参与
#
软件开发2024笔面经
#
2326048次浏览
48226人参与
#
如果中了500万,你会离职吗?
#
13723次浏览
145人参与
#
如何一边实习一边秋招
#
1000215次浏览
12699人参与
牛客网
牛客企业服务