5亿个数中找到中位数

问题

有5亿个整数,没有排序。找到他们的中位数

思路

使用双层桶划分(分而治之)的策略。假设题目中指的是32位的无符号整数,共有2 ^ 32个数字。
我们将2 ^ 32这个范围划分成2 ^ 10个区域。对数据进行第一次扫描,统计各个落到各个区域内的数字的个数。
第一次扫描后,通过统计就可以知道,中位数在哪个区域内,以及它是这个区域的第几大的数字。
进行第二次扫描,这次只统计落到目标区域内的数字,同时结合Bitmap记录都出现了哪些数字。最后通过Bitmap和第一次扫描的结论,就可以找到那个中位数了。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 教你如何迅速秒杀掉:99%的海量数据处理面试题 本文经过大量细致的优化后,收录于我的新书《编程之法》第六章中,新书...
    Helen_Cat阅读 12,118评论 1 39
  • 摘要:本文将向您讲述诸多数据处理面试题以及方法的总结。 第一部分、十道海量数据处理面试题 1、海量日志数据,提取出...
    拾壹北阅读 5,625评论 0 28
  • 第一部分、十道海量数据处理面试题 1、海量日志数据,提取出某日访问百度次数最多的那个IP。 此题,在我之前的一篇文...
    零一间阅读 4,496评论 0 5
  • (一)——开篇 大数据量的问题是很多面试笔试中经常出现的问题,比如baidu google 腾讯 这样的一些涉及到...
    零一间阅读 4,082评论 0 5
  • 上周五上映《烟花》,宝想看,也突发奇想要单独行动,放学后约同学一起吃晚饭,一起看电影。好吧,小人儿长大了。她电话给...
    绵绵羊_6461阅读 3,465评论 0 0