算法问题，大神进！

[williamjing]

问：如何用 512MB 内存对 4 亿个银行卡号（每个卡号 16 位阿拉伯数字）进行搜索？

[lululau]

硬盘多大？

[himarrin]

忙猜 bitmap

[Jooooooooo]

搜索指的是?

[cnoder]

找最大 /最小的 n 个是经典题

[siriussilen]

字典树呗…

[xiao109]

我感觉这些算法题都是三板斧，就那几个固定的套路

[stone666]

布隆过滤器

[williamjing]

@lululau 不允许用其他条件，只能在内存中操作。

[williamjing]

@Jooooooooo 给定一个卡号，查看是否在其中。

[williamjing]

@siriussilen 具体讲讲？

[williamjing]

@xiao109 给个思路？

[williamjing]

@stone666 有误识别率，有没有一个完全准确的算法？

[TomVista]

一个深度 16 的 10 叉 树,

[Jooooooooo]

@williamjing 噢, 搜下布隆过滤器.

[williamjing]

我觉得这个问题可以转换为两个子问题，1. 4 亿个卡号如何存储； 2. 查找。解决了存储问题也就解决了查找问题。

[sNullp]

512M = 512*1024*1024*8 = 4294967296bits

[williamjing]

@himarrin 为了解决存储问题，看来只能往 bitmap 方向考虑。

[williamjing]

@sNullp 对，每个卡号最多只能用 10 bits 来存储。

[sadfQED2]

字典树+1

[sNullp]

@williamjing 每个卡号明明只占 1bit