给定40亿个不重复未排序的整数，如何快速判断一个数是否在40亿个数中？内存限制1GB
I
Fox约 4 分钟
Fox约 4 分钟题目描述
给定40亿个不重复的unsigned int的整数，没有排过序，给定一个数，如何快速判断它是否在这40亿个数中？内存限制：1GB
解决方案对比
推荐方案
在给定的内存限制下，位图法是最直接且高效的方法。它能够准确地判断一个数是否存在，而不需要额外的计算开销。
解析思路
1. 位图法
建立位图标记数字
由于unsigned int的范围是[0, 1 << 32)，即0到4,294,967,295，我们需要4,294,967,296个bit来表示每个数字。每个bit对应一个整数，初始时所有bit均为0。
直接查询位图
读取这40亿个整数，将对应的bit设置为1。然后读取要查询的数，查看相应bit是否为1，如果为1表示存在，如果为0表示不存在。
2. 布隆过滤器
用多个hash函数
布隆过滤器通过多个哈希函数将元素映射到一个位数组中。每个哈希函数将元素映射到不同的位置，并将这些位置的bit设置为1。
允许小概率误判
布隆过滤器允许小概率的误判，即可能会错误地认为一个不存在的元素存在（假阳性），但不会错误地认为一个存在的元素不存在（假阴性）。
详细实现
1. 位图法实现
内存需求
4,294,967,296个bit ≈ 512MB
由于内存限制为1GB，完全满足要求
实现步骤
创建一个大小为512MB的位数组，初始时所有bit均为0 遍历这40亿个整数，对于每个整数，将其对应的bit位置为1 对于要查询的数，检查其对应的bit位置是否为1
#include<iostream>#include<vector>const int MAX_NUM = 1 << 30; // 4,294,967,296 / 32std::vector<unsignedint> bitmap(MAX_NUM, 0);voidsetBit(unsignedint num){int index = num / 32;int bit = num % 32;bitmap[index] |= (1 << bit);}boolcheckBit(unsignedint num){int index = num / 32;int bit = num % 32;return (bitmap[index] & (1 << bit)) != 0;}intmain(){// 假设我们有40亿个整数存储在数组nums中std::vector<unsigned int> nums = {/* 40亿个整数 */};// 设置位图for (unsigned int num : nums) {setBit(num);}// 查询某个数是否存在unsigned int queryNum = 123456789;if (checkBit(queryNum)) {std::cout << "Number exists." << std::endl;} else {std::cout << "Number does not exist." << std::endl;}return 0;}
2. 布隆过滤器实现
内存需求
根据误判率进行调整，通常远小于位图法。
内存需求约为位图法的1/10，但允许一定的误判率
实现步骤
选择合适的哈希函数数量和位数组大小 将40亿个整数通过多个哈希函数映射到位数组中 对于要查询的数，通过相同的哈希函数计算其映射位置 检查这些位置是否均为1，判断是否存在
#include<array>#include<vector>#include<functional>#include<random>const size_t BIT_ARRAY_SIZE = 100000000; // 1亿位const size_t HASH_COUNT = 5; // 5个哈希函数std::array<std::vector<bool>, HASH_COUNT> bloomFilter(BIT_ARRAY_SIZE);std::array<std::hash<unsigned int>, HASH_COUNT> hashFunctions;voidsetBit(unsignedint num){for (size_t i = 0; i < HASH_COUNT; i++) {size_t index = hashFunctions[i](num) % BIT_ARRAY_SIZE;bloomFilter[i][index] = true;}}boolcheckBit(unsignedint num){for (size_t i = 0; i < HASH_COUNT; i++) {size_t index = hashFunctions[i](num) % BIT_ARRAY_SIZE;if (!bloomFilter[i][index]) return false;}return true;}intmain(){// 初始化哈希函数hashFunctions[0] = std::hash<unsigned int>();hashFunctions[1] = std::hash<unsigned int>();hashFunctions[2] = std::hash<unsigned int>();hashFunctions[3] = std::hash<unsigned int>();hashFunctions[4] = std::hash<unsigned int>();// 初始化布隆过滤器for (size_t i = 0; i < HASH_COUNT; i++) {bloomFilter[i] = std::vector<bool>(BIT_ARRAY_SIZE, false);}// 假设我们有40亿个整数// 读取这些整数并设置位// ...// 查询某个数是否存在unsigned int queryNum = 123456789;if (checkBit(queryNum)) {std::cout << "Number might exist (false positive possible)." << std::endl;} else {std::cout << "Number definitely does not exist." << std::endl;}return 0;}
性能分析
结论
在给定的内存限制下，位图法是最直接且高效的方法。它能够准确地判断一个数是否存在，而不需要额外的计算开销。
布隆过滤器虽然可以节省内存，但允许一定的误判率，适用于对误判率可以接受的场景。
位图法利用了位运算的高效性，能够在常数时间内完成查询操作，非常适合处理大规模数据集。