首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
一个数据表有51233个元素,如果仅要求找出其中最大的12个
[单选题]
一个数据表有51233个元素,如果仅要求找出其中最大的12个元素,采用什么算法比较节省时间 ( )。
堆排序
希尔排序
快速排序
直接选择排序
查看正确选项
添加笔记
求解答(0)
邀请回答
收藏(27)
分享
纠错
3个回答
添加回答
4
neekity
TopK问题 堆排序
发表于 2019-04-15 19:51:14
回复(0)
0
牛客382468240号
好
发表于 2022-09-06 16:51:46
回复(0)
0
男南楠难
思路1:利用堆排序实现
(1)取前m个元素(例如m=100),建立一个小顶堆。保持一个小顶堆得性质的步骤,运行时间为O(lgm);建立一个小顶堆运行时间为m*O(lgm)=O(m lgm);
(2)顺序读取后续元素,直到结束。每次读取一个元素,如果该元素比堆顶元素小,直接丢弃。如果大于堆顶元素,则用该元素替换堆顶元素,然后保持最小堆性质。最坏情况是每次都需要替换掉堆顶的最小元素,因此需要维护堆的代价为(N-m)*O(lgm);最后这个堆中的元素就是10亿个数据中最大的100个。时间复杂度为O(N lgm)。
发表于 2019-04-15 20:23:06
回复(1)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
C++工程师
系统工程师
算法工程师
2019
小鹏汽车
排序
Java工程师
来自:
小鹏汽车2019春招车...
上传者:
小小
难度:
3条回答
27收藏
3296浏览
热门推荐
相关试题
(verbal)最近的研究显示,许...
言语理解与表达
2019
普华永道
人力资源
审计
税务服务
风险管理
管理咨询
行政管理
评论
(2)
来自
职能类模拟题14
下面哪些方法有助于解决深度网络的梯...
自然语言处理
算法工程师
小鹏汽车
2019
评论
(8)
来自
小鹏汽车2019春招NL...
在金属发展史上,从陨铁的的锻制到人...
数据库工程师
搜狐畅游
游戏策划
游戏工程师
市场
2020
公关
商务
财务
人力资源
项目经理
系统工程师
评论
(1)
有变量int i = 0; int...
Java
评论
(31)
来自
小鹏汽车2019春招车联...
关于 ACID 说法不正确的是(&...
数据库
Java工程师
C++工程师
算法工程师
小鹏汽车
2019
系统工程师
评论
(4)
来自
小鹏汽车2019春招车联...
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题