Skip to content

Latest commit

 

History

History
21 lines (11 loc) · 903 Bytes

find-a-number-if-exists.md

File metadata and controls

21 lines (11 loc) · 903 Bytes

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

题目描述

给定 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 表示不存在。

方法总结

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