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) 快排思想
相关推荐
牛客上的彭于晏：过来人告诉你，入职后要做的第一件事儿不是说主动找活儿做，你要先学会融入团队，摸清ld的性格，投其所好。然后才是展示你的能力，能力上可以说技术或者业务，以业务能力为主，技术能力为辅。优先保证自己对业务需求的开发保证质量效率，然后再谈技术的问题，不要你觉得啥啥啥不行就想着整体优化了（发现校招生最喜欢干这事儿），我工作快5年了发现搞这种的最后都没啥好的结果，产出没有还引入新的bug，校招或者实习的水平看到的问题别人看不到嘛？为什么别人不去搞？浪费时间还没收益的事儿不要去做，技术上的能力体现在对于一个新需求，在不符合现在业务发展的架构设计上，你能拿出好的技术方案同时能考虑到后续业务发展逐渐将技术架构引入合理的架构，这是一个漫长的过程而不是一次性的 点赞 评论 收藏
分享
许长渭：这也不算翻脸啊 你要觉得她态度不好直接在微信上说他不就行了 没必要当面一套背后一套 点赞 评论 收藏
分享
