n个数值选出最大m个数（3<m<n）的最小算法复杂度是多少？
为什么不可以先建一个大小为n的大顶堆，然后从调整m次堆，复杂度就是就m*logn吗？
leetcode上的解法是建一个m大小的小顶堆，调整n词，复杂度是n*logm
到底哪个更优啊
2016-09-08 16:44 已编辑 C++
关注
全部评论
牛客399835号
Java
用快速选择算法平均时间复杂度为O(n)，还可以用Median of medians，也叫BRPRT算法可以保证是O(n)的
送花
回复
分享
heda
算法工程师
部分快排 时间复杂度 O(N) 存储复杂度 O(N)
堆排序 时间复杂度 O(NlogM) 空间复杂度 O(M)
这题没啥好说的，也没有正确答案，答出第一个，面试官会问你如果内存存不下整个数组怎么办，答出第二个，面试官会问你有没有更快的。都被问到好几次了
送花
回复
分享
秋招专场
校招火热招聘中
官网直投
--海-星--
快手_软件开发工程师
最小复杂度 O(N) 快排思想
送花
回复
分享
你好，天朝
C++
当N足够大时，建大小为n的方法优
送花
回复
分享
./a.out
C++
支持一楼的，BFPRT算法可以保证O(N)的复杂度，在O（N）的复杂度先选出第K大的数，之后再遍历一遍选出比第K大的数小的数，复杂度还是O（N）
送花
回复
分享
牛客1481368号 楼主
楼主 C++
牛客网上给的答案是nlogm O(n)答案不对 按照楼上的意思是O（mn）
送花
回复
分享
一只补习的Fyu
C工程师
建小顶堆，你求M个最大的，保证堆顶是M个中最小的，复杂度是O（nlogm），你不可能比n小，怎么也得遍历一遍吧。
送花
回复
分享
相关推荐
阿里云HR面92人在聊 点赞 评论 收藏
转发
查看4道真题和解析