32位无符号整数的范围是0 ~ 4 294 967 295,现在有一个正好包含40亿个无符号整数的文件,所以在整个范围中必然有未出现过的数。怎么找到所有未出现过的数?
要求: 可以使用最多1GB的内存。
进阶: 内存限制10MB,但是只用找到一个没出现过的数即可。
常规方法:假设用哈希表来保存出现过的数,那么如果40亿个数都不同,则哈希表的记录数为40亿条,存一个32位整数需要4B,所以最差情况下需要40亿×4B = 160亿字节,大约需要16GB的空间,不符合要求。
思路:
① 使用bit m