美文网首页
从10G个数中找到中数在一个文件中有10G个整数,乱序排列,要求

从10G个数中找到中数在一个文件中有10G个整数,乱序排列,要求

作者: 面试题小能手 | 来源:发表于2020-04-12 15:44 被阅读0次

不妨假设10G个整数是64bit的。

2G内存可以存放256M个64bit整数。

我们可以将64bit的整数空间平均分成256M个取值范围,用2G的内存对每个取值范围内出现整数个数进行统计。这样遍历一边10G整数后,我们便知道中数在那个范围内出现,以及这个范围内总共出现了多少个整数。

如果中数所在范围出现的整数比较少,我们就可以对这个范围内的整数进行排序,找到中数。如果这个范围还可以采用同样的方法将此范围再次分成多个更小的范围(256M-228,所以最多需要3次就可以将此范围缩小到1,也就找到了中数)

相关文章

  • 大数据问题处理

    一、在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。解决方案:桶排序。1、读入内存2G...

  • (2)BitMap原理

    经常能够看到有些大厂的面试题里有一些这样的题目:一个10G的文件,里面全部是自然数,一行一个,乱序排列,对其排序。...

  • BitMap原理

    经常能够看到有些大厂的面试题里有一些这样的题目:一个10G的文件,里面全部是自然数,一行一个,乱序排列,对其排序。...

  • 海量数据找中位数

    题目只有2G内存的pc机,在一个存有10G个整数的文件,从中找到中位数,写一个算法。 思路一:外排序(排序-归并)...

  • 《编程珠玑》第一章

    案例:一个最多包含n个正整数的磁盘文件,每个数都小于n,其中n=10^7,文件中不包含重复的数。要求输出按升序排列...

  • 关于mapReduce过程解释以及疑惑,欢迎吐槽与解读

    首先当我在hdfs上存入一个很大的10g文件的时候,首先10g文件会按照128分成80个block,假设我有10个...

  • Python求“从1到100的整数中随机10个,和为100的组合

    有一个这样的需求,要求从1到100的整数中随机取10个数,并且10个数的和要求是100,那么这样的组合有哪些? 直...

  • 剑指 Offer II 006. 排序数组中两个数字之和

    给定一个已按照 升序排列 的整数数组 numbers ,请你从数组中找出两个数满足相加之和等于目标数 targe...

  • 9.JavaScript-运算符练习

    需求:要求用户输入一个整数,判断这个数是否在100~200之间的数 需求:要求用户输入两个整数,找出最大的那个数之...

  • c#练手code

    做一个控制台程序,要求输入三个任意整数,将三个数按从大到小的顺序输出。 根据排列组合,知道有6中情况,一是可以采用...

网友评论

      本文标题:从10G个数中找到中数在一个文件中有10G个整数,乱序排列,要求

      本文链接:https://www.haomeiwen.com/subject/bbtnmhtx.html