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

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,510^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-6710886437的下标对应位置置为1.最后这个数组中没有成为1的就是没出现的,然后在把他转化正真的下标就可以了.
  至于为什么设成64个分组,是因为10MB的限制,只有当设置成64,让40亿/64,这个值才有可能小于10MB.
  我们看一下书中的总结:
  图片.png
  图片.png