首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >100亿个数中寻找中位数

100亿个数中寻找中位数

作者头像
小土豆Yuki
发布2022-12-01 21:25:28
2410
发布2022-12-01 21:25:28
举报
文章被收录于专栏:洁癖是一只狗洁癖是一只狗

在一个大文件中有100亿个32位整数,乱序排列,要求找出中位数;内存限制为512M;请写出算法设计思路;

思路分析

中位数的意思就是,如果是个数是奇数,则取中间的那个数字,如果是偶数,则取中间的两位数的平均值

512M,只能存储大概1亿数据,一个int占4个字节

512M=512*1024*1024(byte)/4(byte)=134217728(1亿)

所以常规的排序肯定不能满足常规排序,因此我们需要分成100组,每一组1亿个数

基本思路

  • 首先我们知道一个int,取值范围是[-2^31,2^31-1],可以取4294967296个值,大约43亿,此时我们把这个43亿分成10w个区间,每个区间有43000个数,即[-2^31,-2^31+43000),将a1的区间[-2^31,-2^31+43000),a2的区间[-2^31+43000,-2^31+86000)......一直到a100000的区间;
  • 此时先加载一个亿的数据到内存,然后比较这1亿数据到底放到哪个区间内,记录每个区间可以存放数字的个数.以此类推加载剩余的99亿数据
  • 我们再依次计算每个区间的个数进行累计Sum,当Sum>50亿的时候,最后的这个区间就是存放第50亿个数据的区间,即ai区间,此时记录ai区间前的区间的累计个数为第first个数据
  • 此时我们在对ai区间进行计数,这个区间一共有43000个数字,我们把每一个数字当做一个区间,即43000个区间
  • 同理,我依次把100亿的数据加载到内存,然后判断在ai中的哪个区间,且同样记录每个区间的个数
  • 同样的,把ai的每个区间的个数进行累加,直到Sum大于50亿-first的时候,这个ai对应区间数字就是我们要寻找的第50亿的位置,而下一位就是50亿+1位
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2022-11-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 洁癖是一只狗 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档