n个数值选出最大m个数(3<m<n)的最小算法复杂度是多少?

为什么不可以先建一个大小为n的大顶堆,然后从调整m次堆,复杂度就是就m*logn吗?
leetcode上的解法是建一个m大小的小顶堆,调整n词,复杂度是n*logm
到底哪个更优啊
全部评论
部分快排 时间复杂度 O(N)  存储复杂度 O(N) 堆排序 时间复杂度 O(NlogM)  空间复杂度 O(M)  这题没啥好说的,也没有正确答案,答出第一个,面试官会问你如果内存存不下整个数组怎么办,答出第二个,面试官会问你有没有更快的。都被问到好几次了
1 回复 分享
发布于 2016-09-09 09:50
用快速选择算法平均时间复杂度为O(n),还可以用Median of medians,也叫BRPRT算法可以保证是O(n)的
点赞 回复 分享
发布于 2016-09-08 16:50
建小顶堆,你求M个最大的,保证堆顶是M个中最小的,复杂度是O(nlogm),你不可能比n小,怎么也得遍历一遍吧。
点赞 回复 分享
发布于 2016-09-09 13:25
牛客网上给的答案是nlogm O(n)答案不对 按照楼上的意思是O(mn)
点赞 回复 分享
发布于 2016-09-09 08:34
支持一楼的,BFPRT算法可以保证O(N)的复杂度,在O(N)的复杂度先选出第K大的数,之后再遍历一遍选出比第K大的数小的数,复杂度还是O(N)
点赞 回复 分享
发布于 2016-09-08 22:30
当N足够大时,建大小为n的方法优
点赞 回复 分享
发布于 2016-09-08 20:06
最小复杂度 O(N) 快排思想
点赞 回复 分享
发布于 2016-09-08 19:51

相关推荐

09-09 16:12
已编辑
西南石油大学 Java
future0210:学java就是好啊,啥都能转
点赞 评论 收藏
分享
09-16 14:43
已编辑
江娱互动_研发_客户端开发
背景&nbsp;双一流本硕&nbsp;双非大圆满&nbsp;只找游戏开发相关的岗位。&nbsp;8&nbsp;月初开始秋招到现在&nbsp;投了四五十家吧,&nbsp;目前两&nbsp;offer,&nbsp;不打算继续投了,把剩下的流程走完就开始沉淀了。目前两&nbsp;offer&nbsp;一个是网易互娱测开&nbsp;base&nbsp;广州,一个是江娱互动客户端开发&nbsp;base&nbsp;北京。应该确定网易这个了,说实话北京这个我挺想去的,这家的产品和工作氛围我了解了也不错,是那种踏实做事的,可惜我是广东人。网易的测开是调剂的二志愿,看了下有内部转岗机会,所以打算后面找个时间提前实习,沉淀下再做一个&nbsp;demo&nbsp;作品,写一些&nbsp;shader,增强下图形学渲染的能力,再学点编辑器开发。看到时候内部转岗或者春招继续投客户端开发这样。后面还能再动摇的话应该就灵犀或者腾子了吧(假如这两家确认的是客户端开发岗的话)。-----------------------补下timeline网易互娱&nbsp;测开&nbsp;8.2笔试&nbsp;&nbsp;8.21&nbsp;技术面&nbsp;&nbsp;8.29&nbsp;leader&amp;HRBP面(终面)&nbsp;9.8&nbsp;录用审核(之前一直显示面试中)9.14&nbsp;oc江娱互动&nbsp;客户端开发&nbsp;8.29主程面&nbsp;9.3&nbsp;制作人面&nbsp;9.5&nbsp;BOSS面&nbsp;9.11&nbsp;口头OC&nbsp;9.15&nbsp;正式offer后面考虑了一下&nbsp;&nbsp;感觉还是能走开发就开发吧,测开不太感兴趣,要内部活水转岗还要满1年才能申请。。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务