find-a-number-if-exists

如何在大量的数据中判断一个数是否存在？

题目描述

给定 40 亿个不重复的没排过序的 unsigned int 型整数，然后再给定一个数，如何快速判断这个数是否在这 40 亿个整数当中？

解答思路

方法一：分治法

依然可以用分治法解决，方法与前面类似，就不再次赘述了。

方法二：位图法

由于 unsigned int 数字的范围是 [0, 1 << 32)，我们用 1<<32=4,294,967,296 个 bit 来表示每个数字。初始位均为 0，那么总共需要内存：4,294,967,296b≈512M。

我们读取这 40 亿个整数，将对应的 bit 设置为 1。接着读取要查询的数，查看相应位是否为 1，如果为 1 表示存在，如果为 0 表示不存在。

方法总结

判断数字是否存在、判断数字是否重复的问题，位图法是一种非常高效的方法。