基本思路:将数字存入 set 集合中并不是一个很好的选择,占用的空间太大。这里可以使用 bitmap 数据结构来解决这个问题。

32 位机器上,对于一个整型数,比如int a=1 在内存中占 32bit 位,这是为了方便计算机的运算。但是对于某些应用场景而言,这属于一种巨大的浪费,因为我们可以用对应的 32bit 位对应存储十进制的 0-31 个数,而这就是 Bit-map 的基本思想。Bit-map 算法利用这种思想处理大量数据的排序、查询以及去重。

bitmap 快速查找

我们可以申请一个 2^32 的空间(约42亿),然后我们对所有数字进行一次遍历,然后将相应的状态位修改为 1,遍历完成后我们就就可以进行查询了。由于我们是的数字是连贯的,所以我们可以用一种分桶查找的思想来进行快查找,可以对目标值除以 32(定位到对应的桶),然后再取余,这样就可以定位到相应的状态位。如果状态位为 1,则目标值重复,如果为 0,则目标值不重复。

bitmap 快速的去重

思路和上面的基本一样,甚至我们可以为每个位分配 2bits,假定数字不存在为 00,存在一次为 01,存在两次及以上为 11。最后我们可以对状态位进行统计, 就可以得到不重复的数字个数了,时间复杂度为 O(n)。

使用 Bit-map 的思想,我们可以将存储空间进行压缩,而且可以对数字进行快速排序、去重和查询的操作。Bloom Fliter 是 Bit-map 思想的一种扩展,它可以在允许低错误率的场景下,大大地进行空间压缩,是一种拿错误率换取空间的数据结构。