【C++干货铺】哈希结构的应用：位图 | 布隆过滤器 | 海量数据处理

作者：IT小白 | 2024-07-18 20:31:13

踩

位图

一道面试题

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在
这40亿个数中。【腾讯】

解决方案：

从头到尾遍历这40亿个数。时间复杂度 $O(N)$

排序( $O(N*\log 2^N)$ ) + 二分查找 $(\log N)$

其实这里最大的问题是这40亿个整数将近16个G的大小；如果我们要是使用搜索较快的数据结构set，底层为红黑树；红黑树中每个结点又含有各种指针，数据量远远不止16个

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】