40亿不重复的正整数，如何判断一个数是否在其中

int型的表示范围为 -2^32~2^32-1 ,也就是40亿多点。
如果只是找一个数在不在其中，则可以直接遍历一次，这是最快速的方法。

如果要是判断多个数是否在其中，则遍历多次效率就很低了，首先4*10^9 bit 约等于512M字节，因此首先可以在内存中开512M的空间，创建一个数组a，遍历一次40亿个数，将数组下标为这个数的位置1，如遍历到2000000111这个数，则直接将a[2000000111]置1。 在查询某个数在不在其中，直接取数组的那个位置数据判断如果是1则表示在，0表示不在。

这个方法叫做位图法 bitmap， 在判断多个数在不在其中的时候效率很高。

参考：csdn

评论

1 楼 lg_asus 2012-02-08  

文章中说错了：
如果只是找一个数在不在其中，则可以直接遍历一次，这是最快速的方法。

40亿数据太大，是不能放在内存中的，还是采用bitmap方法。