算法问题，大神进！

2022 年 2 月 11 日
 williamjing
问：如何用 512MB 内存对 4 亿个银行卡号（每个卡号 16 位阿拉伯数字）进行搜索？
5749 次点击
所在节点    算法
76 条回复
lululau
2022 年 2 月 11 日
硬盘多大？
himarrin
2022 年 2 月 11 日
忙猜 bitmap
Jooooooooo
2022 年 2 月 11 日
搜索指的是?
cnoder
2022 年 2 月 11 日
找最大 /最小的 n 个是经典题
siriussilen
2022 年 2 月 11 日
字典树呗…
xiao109
2022 年 2 月 11 日
我感觉这些算法题都是三板斧，就那几个固定的套路
stone666
2022 年 2 月 11 日
布隆过滤器
williamjing
2022 年 2 月 11 日
@lululau 不允许用其他条件，只能在内存中操作。
williamjing
2022 年 2 月 11 日
@Jooooooooo 给定一个卡号，查看是否在其中。
williamjing
2022 年 2 月 11 日
@siriussilen 具体讲讲？
williamjing
2022 年 2 月 11 日
@xiao109 给个思路？
williamjing
2022 年 2 月 11 日
@stone666 有误识别率，有没有一个完全准确的算法？
TomVista
2022 年 2 月 11 日
一个深度 16 的 10 叉 树,
Jooooooooo
2022 年 2 月 11 日
@williamjing 噢, 搜下布隆过滤器.
williamjing
2022 年 2 月 11 日
我觉得这个问题可以转换为两个子问题，1. 4 亿个卡号如何存储； 2. 查找。解决了存储问题也就解决了查找问题。
sNullp
2022 年 2 月 11 日
512M = 512*1024*1024*8 = 4294967296bits
williamjing
2022 年 2 月 11 日
@himarrin 为了解决存储问题，看来只能往 bitmap 方向考虑。
williamjing
2022 年 2 月 11 日
@sNullp 对，每个卡号最多只能用 10 bits 来存储。
sadfQED2
2022 年 2 月 11 日
字典树+1
sNullp
2022 年 2 月 11 日
@williamjing 每个卡号明明只占 1bit

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://study.congcong.us/t/833123

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX