美文网首页
40亿个非负整数中找到没有出现过的数

40亿个非负整数中找到没有出现过的数

作者: chengcongyue | 来源:发表于2019-04-16 20:22 被阅读0次

32位无符号数的范围是0---4294967295,现在有一个包括40亿个无符号整数的文件,所以在整个范围中肯定有没有出现过的数.可以最多使用1GB的内存,怎么找到所有没有出现过的数?
进阶:内存限制为10MB,只用找到一个没有出现过的数就可以.

原问题

32的范围是大搞42亿,现在有40亿个32位无符号整数,所以在0----42亿多,肯定有这个文件中不存在的.
如果使用hashMap来保存40亿个无符号整数的文件,极端情况下有40亿个数,记录有40亿条,32位整数有4B,最差情况是4B40亿=160亿个字节,16GB的空间,这个肯定是不符合规则的.
我们可以通过bit map来解决这个问题.申请一个长度为4294967295的bit数组,即每一位是0或者1,其所占空间的大小为42亿bit,5亿B,5
10^8N,500MB,500MB满足空间大小的需求.
然后遍历40亿个数,如果这个数出现过,就在bit map下标对应位置置1,如果在40亿中遇到了7000,那么在bit map中bitArr[7000]置为1.
然后就是遍历bit map,其中为0的,对应的下标就是没出现过的.然后没出现的数就找出来了.

进阶问题

只有10MB,这个时候只要找出一个没出现过的数就可以了.先说解法,最后在说每一步的含义.

  • 将0---4294967295这个数平均分成64个取件,每个区间有67108864.每个区间大概如下: 图片.png
    这个就涵盖了42亿个数了,因为一共有40亿个数,然后我们遍历40亿个数,有的数放在对应的区间,最后肯定会有区间小于67108864,通过这一点就可以找到没出现过的数.
    然后
    第一次遍历,先申请64个整型数组countArr[0..63],countArr[i]表示第i个区间上的数,遍历完40亿个数之后,肯定会有区间小于67108864的.这个时候使用的内存是644B,内存容量没有超过10MB.
    我们来看看书中是怎么写的.
    图片.png
    假设我们现在得到了一个区间,满足小于67108864这个条件(区间37).然后就有了第二次遍历的过程,申请一个67108864的bit map,这时候大概有8MB.然后在遍历40亿个数,只关注位于37区间的(通过映射当前位置/67108864==37).
    如果存在的话,我们就把num-67108864
    37的下标对应位置置为1.最后这个数组中没有成为1的就是没出现的,然后在把他转化正真的下标就可以了.
    至于为什么设成64个分组,是因为10MB的限制,只有当设置成64,让40亿/64,这个值才有可能小于10MB.
    我们看一下书中的总结:
    图片.png
    图片.png

相关文章

  • 40亿个非负整数中找到没有出现过的数

    32位无符号数的范围是0---4294967295,现在有一个包括40亿个无符号整数的文件,所以在整个范围中肯定有...

  • Day36 加一

    给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一 https://leetcode-cn....

  • LeetCode 2. 两数相加(Add Two Numbers

    2. 两数相加 切题 一、Clarification 1、明确题目 链表、非空、非负的整数、逆序、每个节点只能存储...

  • BigData

    只用2GB内存在20亿个整数中找到出现次数最多的数 解法:哈希表? key代表整数,value代表这个数出现的次数...

  • 正则表达式的使用

    非负整数:^\d+$ 正整数:^[0-9][1-9][0-9]$ 非正整数:^((-\d+)|(0+))$ 负整数...

  • 常见正则表达式

    非负整数:^\d+$ 正整数:^[0-9][1-9][0-9]$ 非正整数:^((-\d+)|(0+))$ 负整数...

  • 常用的正则表达式整理

    非负整数:^\d+$ 正整数:^[0-9][1-9][0-9]$ 非正整数:^((-\d+)|(0+))$ 负整数...

  • 思维导图初中数学第一章1.2有理数

    (1)有理数的定义:正整数0负整数统称为整数:正分数、负分数统称为分数.整数和分数统称为有理数. (2)有理数的分...

  • 附录

    非负整数:^\d+$ 正整数:^[0-9]*[1-9][0-9]*$ 非正整数:^((-\d+)|(0+))$ 负...

  • 66.加一

    一、题目原型: 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。最高位数字存放在数组的首位, 数...

网友评论

      本文标题:40亿个非负整数中找到没有出现过的数

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