博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
利用最小堆找出10亿个数中最大的10000个数
阅读量:5061 次
发布时间:2019-06-12

本文共 419 字,大约阅读时间需要 1 分钟。

最小堆

最小堆是一种完全二叉树,特点是根节点比两个子节点都小(或者根节点比子节点都大)

过程

  • 先找10000个数构建最小堆
  • 依次遍历10亿个数,如果比最小堆的最小值大,则替换这个最小值,并重新构建最小堆
  • 最后输入10000个值
  • 时间复杂度
    构建最小堆的复杂度为 logn,求出最大m个数会构建m次最小堆,时间复杂度为 m logm, 这里m为10000
    进行n次时间复杂度为n,这里n为10亿,总时间复杂度为 n m logm,即10亿 10000 log 10000

其他算法

  • 将十亿个数排序,找出最大值,但是占用空间比较大,做了很多无用功
  • 分治法:将10亿个数分成10份,求出每份的前10000个数 ,然后在这个10 * 10000 个数中找出最大的10000个数
  • hash去重复,将这10亿个数的Hash值进行比较,去除重复的

转载于:https://www.cnblogs.com/bincoding/p/8975802.html

你可能感兴趣的文章
java-动态规划算法学习笔记
查看>>
STL容器之vector
查看>>
Linux 内核中断内幕
查看>>
DNS负载均衡
查看>>
无法向会话状态服务器发出会话状态请求
查看>>
数据中心虚拟化技术
查看>>
Oracle OEM 配置报错: No value was set for the parameter DBCONTROL_HTTP_PORT 解决方法
查看>>
01入门
查看>>
python正则表达式
查看>>
嵌套循环连接(nested loops join)原理
查看>>
shell统计特征数量
查看>>
复习文件操作
查看>>
C#Hashtable与Dictionary性能
查看>>
10个让你忘记 Flash 的 HTML5 应用演示
查看>>
8个Python面试必考的题目,小编也被坑过 ToT
查看>>
SQL Server 使用作业设置定时任务之一(转载)
查看>>
centos 图形界面和命令行界面切换(转载)
查看>>
Maven启用代理访问
查看>>
Primary definition
查看>>
第二阶段冲刺-01
查看>>