page contents
首页 问答
正文

腾讯笔试题：从10G个数中找到中数 在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。

轩辕小不懂 发布于 2021-06-07 16:54
阅读 591
收藏 0
答案 1
分类：面试与就业
  • 面试题
    • 默认排序 时间排序

    最佳答案 2021-06-07 16:59

    974
    Pack
    Pack

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

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

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

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

    请先 登录 后评论
    轩辕小不懂
    1 关注
     
    轩辕小不懂
    提出于 2021-06-07 16:54
    全部

    轩辕小不懂 的其他提问

    类似问题

    统计在一个队列中的数字，有多少个正数，多少个负数？
    1 回答
    591 阅读
    给一个数 N，把 2 到 N 之间的素数输出出来？
    1 回答
    591 阅读
    AngularJS和React、Vue有什么区别？结合开发经历描述
    0 回答
    591 阅读
    用 Java 语言实现，在给出的数组中，删除重复项？
    0 回答
    591 阅读
    编写一个递归函数，接收一个数组和一个回调函数（Callback Function），如果该数组的值从该回调函数，返回 True，否则返回 False？
    1 回答
    591 阅读
    编写一个递归函数，接收一个单词数组，并返回一个包含所有大写单词的数组？
    1 回答
    591 阅读