面试高频:查找第k大的数(欢迎补充)

1.查找第k大的数:快速选择法,On(这里讲的都是时间复杂度)。
快速选择法:由于快速排序每次排序都可以用On时间求出基准是第几大的数且左边都比基准小,右边都比基准大。若第一次求出基准是第i大,若ik,以i为右边界递归左边,每次减小一半查找范围,直到i==k,总共时间为On。

2.查找最大k个数(k远小于n):建一个大小为k的优先队列(小根堆),klogk,对于剩下的元素,若大于堆顶则拿掉堆顶最小的再插入,总共用nlogk的时间找到最大k个(堆顶为第k大的)。共计(n+k)logk<2nlogk=nlogk,k很小时视为On,k大时用方法4。

3.频繁查找第k大的数(数组变化):先用方法2找出原始数组最大k个数,klogk,若要新增元素,先对比堆顶,若大于堆顶则先移除堆顶再插入堆,这时堆顶为第k大的数。每次查找复杂度为logn。

4.频繁查找第k大的数(k变化):排序,nlogn,每次查找时间为O1。

5.查找a~b之间的所有元素:先用快速排序法找到第a大和第b大的数,用On,再遍历一次,选出位于这两个数之间的数。总共On。

6.频繁查找,数组和k同时变化:先建一个二叉搜索树nlogn,维护每个结点的子树大小,查k时从根节点开始,若小于左子树大小,直接进入左子树,否则k-=左子树大小后进入右子树,每次查找logn,每次插入时将经过的结点子树大小++,也是logn。

7. 查找数据流的中位数:维护一个最大堆和一个最小堆,满足最大堆所有的数都小于最小堆的数,当两个堆数量相等时,中位数就是堆顶平均,若最大堆比最小堆大1,中位数就是最大堆顶,插入新元素时,奇数次考虑插入最大堆,若大于堆顶则插入最小堆,再把最小堆堆顶插入最大堆。偶数次类似。

#面试题刺客退退退#
全部评论
就是快拍的板子,也可以用计数排序,时间复杂度一样的
点赞 回复 分享
发布于 03-31 09:28 上海
是快速选择吧?
点赞 回复 分享
发布于 03-30 22:35 美国

相关推荐

07-23 11:37
延安大学 C++
绷不住了,晚上十点发拒信,是还在加班吗这样一想挂了好像也没什么不好
码农索隆:这个都是真人发嘛,会用到机器人定时发嘛
点赞 评论 收藏
分享
Lorn的意义:1.你这根本就不会写简历呀,了解太少了 2.你这些项目经历感觉真的没啥亮点啊,描述的不行,重写书写一下让人看到核心,就继续海投 注意七八月份ofer还是比较多的,越往后机会越少,抓住时机,抓紧检查疏漏,加油查看图片
点赞 评论 收藏
分享
代码飞升:别用口语,后端就写后端,前端就写前端,最后别光后悔
点赞 评论 收藏
分享
评论
4
14
分享

创作者周榜

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