n个数值选出最大m个数（3<m<n）的最小算法复杂度是多少？
为什么不可以先建一个大小为n的大顶堆，然后从调整m次堆，复杂度就是就m*logn吗？
leetcode上的解法是建一个m大小的小顶堆，调整n词，复杂度是n*logm
到底哪个更优啊
2016-09-08 16:44 已编辑 东北大学 C++
关注
全部评论
heda
清华大学 算法工程师
部分快排 时间复杂度 O(N) 存储复杂度 O(N)
堆排序 时间复杂度 O(NlogM) 空间复杂度 O(M)
这题没啥好说的，也没有正确答案，答出第一个，面试官会问你如果内存存不下整个数组怎么办，答出第二个，面试官会问你有没有更快的。都被问到好几次了
牛客399835号
还不错的学校 Java
用快速选择算法平均时间复杂度为O(n)，还可以用Median of medians，也叫BRPRT算法可以保证是O(n)的
一只补习的Fyu
左家垅男子职业技术学院 C工程师
建小顶堆，你求M个最大的，保证堆顶是M个中最小的，复杂度是O（nlogm），你不可能比n小，怎么也得遍历一遍吧。
牛客1481368号 楼主
楼主 东北大学 C++
牛客网上给的答案是nlogm O(n)答案不对 按照楼上的意思是O（mn）
./a.out
安徽大学 C++
支持一楼的，BFPRT算法可以保证O(N)的复杂度，在O（N）的复杂度先选出第K大的数，之后再遍历一遍选出比第K大的数小的数，复杂度还是O（N）
你好，天朝
中国科学院大学 C++
当N足够大时，建大小为n的方法优
--海-星--
快手_软件开发工程师
最小复杂度 O(N) 快排思想
相关推荐
06-16 19:09
河南开封科技传媒学院 Java 
牛客83700679...：简历抄别人的，然后再投，有反馈就是简历不行，没反馈就是学历不行，多投多改只要技术不差机会总会有的 点赞 评论 收藏
分享
Lorn的意义：1.你这根本就不会写简历呀，了解太少了
2.你这些项目经历感觉真的没啥亮点啊，描述的不行，重写书写一下让人看到核心，就继续海投
注意七八月份ofer还是比较多的，越往后机会越少，抓住时机，抓紧检查疏漏，加油
查看图片 点赞 评论 收藏
分享
