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) 快排思想
相关推荐
牛客喵🐱：暑期实习/春招进度都在专题汇总页里，还有同阶段同学一起交流 👉https://www.nowcoder.com/link/chunzhaoji2610
查看7道真题和解析 点赞 评论 收藏
分享