首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
牛客8028856号
2017-08-12 22:03
北京理工大学
关注
已关注
取消关注
100w个数中找出最大的100个数
100w个数中找出最大的100个数,求最优解
提示
全部评论
推荐
最新
楼层
鸣月my
华为_消费者云服务部_软件开发工程师
1. 算法如下:根据快速排序划分的思想 (1) 递归对所有数据分成[a,b)b(b,d]两个区间,(b,d]区间内的数都是大于[a,b)区间内的数 (2) 对(b,d]重复(1)操作,直到最右边的区间个数小于100个。注意[a,b)区间不用划分 (3) 返回上一个区间,并返回此区间的数字数目。接着方法仍然是对上一区间的左边进行划分,分为[a2,b2)b2(b2,d2]两个区间,取(b2,d2]区间。如果个数不够,继续(3)操作,如果个数超过100的就重复1操作,直到最后右边只有100个数为止。 2.先取出前100个数,维护一个100个数的最小堆,遍历一遍剩余的元素,在此过程中维护堆就可以了。具体步骤如下: step1:取前m个元素(例如m=100),建立一个小顶堆。保持一个小顶堆得性质的步骤,运行时间为O(lgm);建立一个小顶堆运行时间为m*O(lgm)=O(m lgm); step2:顺序读取后续元素,直到结束。每次读取一个元素,如果该元素比堆顶元素小,直接丢弃 如果大于堆顶元素,则用该元素替换堆顶元素,然后保持最小堆性质。最坏情况是每次都需要替换掉堆顶的最小元素,因此需要维护堆的代价为(N-m)*O(lgm); 最后这个堆中的元素就是前最大的10W个。时间复杂度为O(N lgm)。 3.分块查找 先把100w个数分成100份,每份1w个数。先分别找出每1w个数里面的最大的数,然后比较。找出100个最大的数中的最大的数和最小的数,取最大数的这组的第二大的数,与最小的数比较。。。。
点赞
送花
回复
分享
发布于 2017-08-12 22:41
已注销
建立一个最小堆,一个一个过数据。
点赞
送花
回复
分享
发布于 2017-08-12 22:06
滴滴
校招火热招聘中
官网直投
农药有毒
Java
http://blog.csdn.net/cslbupt/article/details/65935577
点赞
送花
回复
分享
发布于 2017-08-12 23:08
牛客1288965444
Java
按一个数4字节,100万个数也就4m大小,直接小顶堆
点赞
送花
回复
分享
发布于 2017-08-12 22:06
兄弟找我内推呗
字节跳动_UG_算法
100w个数内存可以放置,一般堆排100个没问题啊
点赞
送花
回复
分享
发布于 2017-08-12 22:08
Waitibg
Java
TopK问题
点赞
送花
回复
分享
发布于 2017-08-12 22:22
晚安丶胖不啦叽
C++
最小堆 nlogk
点赞
送花
回复
分享
发布于 2017-08-12 22:26
zhaoyang253
C++
BFPRT算法
点赞
送花
回复
分享
发布于 2017-08-12 23:11
你群最蠢
前端工程师
最小堆或者快排吧
点赞
送花
回复
分享
发布于 2017-08-12 23:51
微信公众号JavaQ
Java
切分、排序、合并排序
点赞
送花
回复
分享
发布于 2017-08-13 07:59
Senix
Java
TopK问题
点赞
送花
回复
分享
发布于 2017-08-13 10:01
rogn
C++
冒泡100次,复杂度1e8,一般的电脑不要1s吧
点赞
送花
回复
分享
发布于 2020-03-05 20:16
牛客652748021号
安卓
快排
点赞
送花
回复
分享
发布于 2020-03-05 20:19
滴滴
校招火热招聘中
官网直投
相关推荐
牛客294836033号
05-17 09:58
门头沟学院 自动化类
项目如何介绍
各位牛客的大佬们,我这学期开始转Java,目前做了个黑马点评,做到用分布式锁解决一人一单这个地方。现在有点好奇就是在面试的时候面试官让我介绍自己的项目的时候应该怎么介绍,感觉做到我目前这个位置为止都没见到有关于点评的内容,就是登录和抢券,好像没有一个完整的业务需求和难点。求大佬们指点一下
点赞
评论
收藏
转发
DRIFT202403141251379
05-13 17:01
已编辑
门头沟学院 计算机类
【详细版】海康威视笔试 5.9 软件开发 实习笔经
拖了好几天,下一个笔试要做了才想起来复盘过了几天记不太清了。首先海康的笔试是随机的,每个人的题不一样,比如我感觉抽到的就挺难的,但看大家情况好像是越简单越容易挂?单选题 18题 每题3分 除了常规计算机基础(相比其他家而言少了很多,没什么408味),有很多数据库、Java基础、框架、设计模式的题,感觉比较杂/细/复古?传统?多选题 4题 每题4分我卷子的部分内容回忆如下:数据库视图,List remove(),IO流,共享锁独占锁,装饰器模式,策略模式,序列化,事务,ArrayList扩容,逻辑运算符/抛空引用异常,Fil...
投递海康威视等公司10个岗位 >
我的实习求职记录
点赞
评论
收藏
转发
胖墩墩的斑马在研究求职打法
05-16 22:20
门头沟学院 计算机类
小红书笔试
不想招人就别发笔试,拉黑了😅
投递小红书等公司10个岗位
点赞
评论
收藏
转发
26加瓦鼠鼠
04-17 15:15
莆田学院 计算机类
够了,我说够了
点赞
评论
收藏
转发
会编程的太平湖水怪就要上岸了
05-15 13:31
重庆理工大学 计算机类
实习应该学到什么东西?
公司技术栈是阿里那一套,但我目前能接触到的只有CRUD,对整个工作流程和系统架构了解尚浅。关键是没有文档可以看......想要看懂系统只能看源码......说实话看起来有点痛苦,多而杂,系统迭代过两次,有些业务逻辑没点时间根本理不清不太清楚该怎么学到东西,现在我的理解是要么学技术栈,要么学业务,但不知道对不对: 1 把微服务技术栈(sofa+k8s)学了 2 把项目核心模块学了(代码杂而多,没文档,难度大,但感觉能啃下来肯定更有帮助)
投递阿里巴巴等公司10个岗位 >
点赞
评论
收藏
转发
点赞
26
评论
分享
回复帖子
全站热榜
1
...
盲审已过,答辩已过,工作已签
1.1W
2
...
5.16校招&实习招聘信息汇总
8585
3
...
实习难求——做个总结
7978
4
...
聪明人看的Java后端入门路线(应该比大多数高手给的靠谱)
7588
5
...
腾讯一面凉经 5.16
5908
6
...
给25届同学: 永远相信美好的事情即将发生
5273
7
...
26届菜鸡投了一个月大厂日常,0面试绷不住了呀。听说9月后机会可能会多起来,感觉要被迫继续沉淀了之前和导师聊,说找到大厂实习的话可以去,对就业帮助大,小厂的话就emmm投了快一个月,老板上打招呼绝大数
5131
8
...
二本漫漫求职路......
3841
9
...
pcg qq 一面
3765
10
...
为什么选择做测试开发
3523
正在热议
#
牛客帮帮团来啦!有问必答
#
760966次浏览
12058人参与
#
海康威视求职进展汇总
#
95921次浏览
1156人参与
#
你的工作大概什么时候入职?
#
3429次浏览
45人参与
#
Offer比较,你最看重什么?
#
51853次浏览
499人参与
#
非技术2024笔面经
#
181683次浏览
3053人参与
#
非技术岗是怎么找实习的
#
76314次浏览
1422人参与
#
实习生应该准时下班吗
#
78910次浏览
582人参与
#
产品实习,你更倾向大公司or小公司
#
37932次浏览
583人参与
#
学历对求职的影响
#
136614次浏览
1553人参与
#
签约/解约注意事项
#
67327次浏览
647人参与
#
今年形式下双非本找得到工作吗
#
7798次浏览
161人参与
#
面试等了一周没回复,还有戏吗
#
41478次浏览
510人参与
#
春招已经启动啦 硬件uu开始投了吗?
#
86620次浏览
678人参与
#
找工作中的意难平
#
191940次浏览
3408人参与
#
百度工作体验
#
24144次浏览
248人参与
#
考研失败就一定是坏事吗?
#
20807次浏览
217人参与
#
2022届毕业生现状
#
321928次浏览
4448人参与
#
华为求职进展汇总
#
524774次浏览
5006人参与
#
正在春招的你,也参与了去年秋招吗?
#
134842次浏览
1699人参与
#
0offer是寒冬太冷还是我太菜
#
419023次浏览
4852人参与
牛客网
牛客企业服务