如何在 40 亿个非负整数中找到未出现的数

备注:待补充bitmap算法链接

题目描述

32 位无符号整数的范围是 0 ~ 4294967295,有一个包含 40 亿个无符号整数的文件,所以在整个范围中必然有未出现过的数。可以使用最多 1GB 的内存,怎么找到所有未出现过的数?

思路分析

假设用 HashSet 来保存出现过的数,那么极端的情况下如果 40 亿个数都不同,则 HashSet 会产生 40 亿条记录。

HashSet一条记录的大小是 4 个字节,那一共需要 160 亿个字节,大约是 16 GB 的内存,明显超出 1GB 内存的限制。

HashSet占用的空间过大,这里我们可以换一种存储的结构,使用 bit 数组来存储数字是否有出现的情况。

具体实现方式是这样的:

首先申请一个长度为 4294967295 的 bit 数组 bitArray,大概是 40 亿个 bit,40 亿 / 8 5 亿字节,0.5 GB 左右,满足内存空间的限制。

而 bit 数组的每一位只有两种状态,为 1 代表这个数字出现过,如果为 0 则代表这个数组没有出现。

其次,遍历这 40 亿个无符号数,例如,遇到 666,就把 bitArray[666] 设置为 1;遇到 888,就把 bitArray[888] 设置为 1。

当遍历完成之后,再依次遍历 bitArray,哪个位置上的值没被设置为 1,就说明这个数不在 40 亿个整数中。例如,发现 bitArray[999] == 0,那么 999 就是没出现过的数。

遍历完 bitArray 之后,就可以找到所有没出现过的数字了。

进阶:内存限制为 10 MB,但是只需要找到一个没出现过的数即可

内存被限制为 10 MB,如果同样继续使用比较节省空间的 bit 数组结构,我们大概只能同时处理 10 MB = 10 000 000 B = 80 000 000 bit(估计计算),也就是说一次大概只能处理八千万个数字。

所以我们需要使用分治的办法来进行处理。

针对这个问题,我们将所有的数字划分区间,先确认没出现过的数是在哪个区间内,再针对这个区间进行查找。

怎么划分区间?

40 亿个数字 / 8 千万,我们可以粗略将其分成 64 个区间来进行处理。

4294967296 / 64 = 67108864,每个区间的大小是 67108864。

怎么确定没出现过的数在哪个区间?

首先,我们可以定义一个大小为 64 的整型数组 count,肯定不会超过 10 MB 的内存限制。

接下来可以对 40 亿个数字进行遍历,例如,遍历到数字 114217728,114217728 / 67108864 == 1,可以确定数字 114217728 是在区间 1,因此 count[1]++;遍历到数字 1857954862,1857954862 / 67108864 == 27,可以确定数字 1857954862 是在区间 27,因此 count[27]++;以此类推。

遍历结束之后,由于只有 40 亿个整数,所以最后肯定会有某个区间的数量会小于 67108864。遍历 count 数组找到这个区间。

确定区间之后,怎么确定是这个区间的哪个数字?

方法也不难,假设我们在前面发现是 count[2] 的值小于 67108864,所以确定是区间 2。

首先,我们可以定义一个大小为 67108864 的 bit 数组 bitArray,六千多万 bit,肯定也不会超过 10 MB 的内存限制。

接下来对 40 亿个数字进行遍历,这次遍历我们只处理区间为 2 的数字,也就是 n / 67108864 == 2 的数字。

当遇到区间为 2 的数字时,例如,遇到了数字 154217728,154217728 % 67108864 == 20000000,因此将 bitArray[20000000] 置为 1。

遍历 40 亿个整数结束之后,我们再遍历 bitArray 数组,找到那个依然为 0 的位置,假设找到的位置是 1000,那么就能确定没出现的数字就是 67108864 * 2 + 1000 == 134218728

总结

这道题我们的核心思想是 bit 数组的结构来存储数字是否有出现过。

对于进阶问题,主要是先确定没出现过的数是在哪个区间,再针对这个区间进行查找。

发表回复

后才能评论