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

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