首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
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-22 00:38
南京大学 Java
深度思考后拒绝了offer
接到offer的那天,我心中矛盾重重,虽然证明了我的能力,但我却不想做不喜欢的工作。经过深思熟虑,我决定拒绝这份看似不错的工作。未来的日子里,我希望能勇敢追求自己真正想做的事情。再过两个月我就25岁了,我不想为不喜欢的选择而后悔。春招见!
牛客创作赏金赛
点赞
评论
收藏
分享
11-21 14:43
360集团_算法
360还能入股吗?
大家千万别嫌找工作麻烦,说实话找了一个糟心的工作,更麻烦,那种每天的过的很压抑的感觉,真的只能辞职了,就和我学弟当初一样,你会发现投简历时偷的懒,等入职之后再办理辞职手续会双倍打回来,我建议至少有四个比较满意的offer了再水,现在多投投,多点选择!公司有免费的三餐,饭量大的可能吃不饱,有健身房,器械不多。但是我喜欢这里的篮球厂,还有台球和乒乓球可以玩。周末来玩玩,再吃点公司得饭挺香的,哈哈哈哈。电梯的话,每天早上要等的比较久,我在6层懒得排队,直接楼梯上去。每天9.30工作到11.30,午休单2点,然后6.30下班,时间不久。新人有12天年假,每个月还有1天不用病假条的病假(累计一年24天假...
360集团公司福利 188人发布
点赞
评论
收藏
分享
11-02 12:31
燕山大学 机械工程师
菜鸡offer选择!
投票
下周做决定,签三方了,麻烦各位了,评论区畅所欲言! #机械人的offer怎么选# #offer帮选# #华为求职进展汇总# 华为引流
Offer来来来2000:
福利:免费饮水。是我理解错了吗
机械人的offer怎么选
offer帮选
点赞
评论
收藏
分享
09-25 23:20
武警特种警察学院 Web前端
甚至没面试🥲
小谷围鸡肉卷阿姨:
+1,腾子投完一动不动
点赞
评论
收藏
分享
11-18 08:49
沈阳工业大学 研发工程师
机考E卷200分题 - 字符串拼接
题目描述:构成指定长度字符串的个数 (本题分值100) 给定 M(0 < M ≤ 30)个字符(a-z),从中取出任意字符(每个字符只能用一次)拼接成长度为 N(0 < N ≤ 5)的字符串, 要求相同的字符不能相邻,计算出给定的字符列表能拼接出多少种满足条件的字符串, 输入非法或者无法拼接出满足条件的字符串则返回0。 输入描述 给定的字符列表和结果字符串长度,中间使用空格(" ")拼接 输出描述 满足条件的字符串个数 用例1 输入 aab 2 1 输出 2 1 说明 只能构成ab,ba。 用例2 输入 abc 2 1 输出 6 1 说明 可以构成:ab...
大厂原题(全网最全,持续...
牛客创作赏金赛
点赞
评论
收藏
分享
点赞成功,聊一聊 >
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
双非本科四年的总结
1.9W
2
...
sagima的阎良出差日记
1.4W
3
...
给正在秋招中枯燥的大家找个乐子听听吧,不被理解真的心寒
1.3W
4
...
浅谈二本Javaer进大厂的感悟
7629
5
...
简历这样写真的很难挂
7590
6
...
收到offer了!!!!
7407
7
...
请大家警惕“总包”骗局!
7065
8
...
提前化身黑子,保温了两次的华为,报批挂了
5710
9
...
双非文科本秋招三个大厂offer 我悟了
5506
10
...
大哥爆发了?
4662
正在热议
#
25届秋招总结
#
263894次浏览
2185人参与
#
0offer是寒冬太冷还是我太菜
#
887417次浏览
7909人参与
#
北方华创开奖
#
23661次浏览
260人参与
#
地方国企笔面经互助
#
2846次浏览
7人参与
#
学历or实习经历,哪个更重要
#
43436次浏览
328人参与
#
选完offer后,你后悔学本专业吗
#
13255次浏览
94人参与
#
查收我的offer竞争力报告
#
19517次浏览
255人参与
#
应届生被毁约被毁意向了怎么办
#
28199次浏览
243人参与
#
你最想要的公司福利是?
#
41865次浏览
146人参与
#
如何一边实习一边秋招
#
987371次浏览
12609人参与
#
一觉醒来,我觉醒了超级打工人系统
#
3305次浏览
36人参与
#
嵌入式转岗的难度怎么样
#
11199次浏览
251人参与
#
你最希望上岸的公司是?
#
76539次浏览
469人参与
#
如何写一份好简历
#
605035次浏览
8509人参与
#
面试体验感最好的是哪家?
#
83649次浏览
818人参与
#
机械应届生薪资要多少才合适?
#
12542次浏览
61人参与
#
牛客十周岁生日快乐
#
48746次浏览
759人参与
#
你认为第一份工作重要吗
#
5446次浏览
49人参与
#
985本硕1个中小厂offer,摆烂or继续努力
#
79942次浏览
589人参与
#
秋招OC许愿
#
228201次浏览
1880人参与
#
来聊聊机械薪资天花板是哪家
#
65735次浏览
445人参与
牛客网
牛客企业服务