1.位图1.1 位图概念及实现面试题 给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中。【腾讯】在不在的问题1.排序二分查找排序是O(NlogN)二分查找是O(logN)2.红黑树3.set/unordered_set2^10 k2^20 M2^30 G1GB2^30B大概是10亿B40亿*4B160亿B也就是16G而如果是红黑树或者set红黑树要存储leftrightparent和color也就是要存4B的int每个结点是20B那么就是16G *580G没有这么大的内存set也要额外开辟空间如果是拉链法要存指针但其实没必要排序和存起来1GB2 ^ 33b我们可以使用位图来解决问题40亿b5亿B0.5G但是我们要开辟的空间是2^32因为无符号数是0~2 ^ 32-1我们用位图的每一位来标识该位对应的数值是否存在类似的计数排序我们开辟空间不是根据数的数量而是数的范围必须要覆盖所有的数 2 ^32/82 ^29B也就是0.5GB但是我们不需要考虑那么多用vector来存储int每个比特位是1一个int就是32int ix/32;int jx%32;#pragmaoncenamespacediy{templatesize_t Nclassbitset{public:voidset(size_t x){intix/32;intjx%32;_t[i]|(1j);//本来是0还是0本来是1还是1第j位置为1}voidreset(size_t x){intix/32;intjx%32;_t[i]~(1j);//~是按位取反除了第j位本来是0还是0本来是1还是1}booltest(size_t x){intix/32;intjx%32;return_t[i](1j);//bool 0为假其余均为真}bitset(){_t.resize(N/321);}private:vectorint_t;};}测试diy::bitset8000bt;diy::bitset0xffffffffbt1;diy::bitset-1bt2;bt.set(1);bt.set(10);bt.set(100);coutbt.test(1)endl;coutbt.test(10)endl;coutbt.test(100)endl;bt.reset(10);bt.set(999);coutbt.test(1)endl;coutbt.test(10)endl;coutbt.test(100)endl;coutbt.test(999)endl;C标准库的bitsethttps://cplusplus.com/reference/bitset/bitset/常用的是testset和reset三个接口1.2 位图应用1.给定 100 亿个整数设计算法找到只出现一次的整数templatesize_t Nclasstwobitset{public:voidset(size_t x){if(!_bt1.test(x)!_bt2.test(x))//00-01_bt2.set(x);elseif(!_bt1.test(x)_bt2.test(x)){//01-10_bt1.set(x);_bt2.reset(x);}//10不做处理 00出现0次10出现1次10出现两次及以上}boolis_once(size_t x){return!_bt1.test(x)_bt2.test(x);//找01}private:bitsetN_bt1;bitsetN_bt2;};测试intmain(){twobitset10tbt;intarr[]{1,2,4,7,9,0,2,4,3,5};for(constinte:arr)tbt.set(e);for(constinte:arr){//只出现一次只会被遍历一次if(tbt.is_once(e))couteendl;}return0;}2.给两个文件分别有 100 亿个整数我们只有 1G 内存如何找到两个文件交集如果用一个位图来标记文件A中存在的数字再用位图去检测文件B的数据是否在位图中这样可能会有重复值比如文件B存在3个5就会检测出三次还要进行去重因为集合是没有重复元素的交集是没有重复元素的所以我们用两个位图diy::bitset20bt1;diy::bitset20bt2;intarr1[]{1,2,4,7,9,0,2,4,3,5};intarr2[]{4,13,2,5,7,2,6,9,1,0,15};for(constinte:arr1)bt1.set(e);for(constinte:arr2)bt2.set(e);for(size_t i0;i20;i){//如果遍历arr1或arr2来测试会出现重复结果if(bt1.test(i)bt2.test(i))coutiendl;}如果出现负数可以考虑映射min映射为0测试输出或者确认结果时映射回来1的变形1 个文件有 100 亿个 int1G 内存设计算法找到出现次数不超过 2 次的所有整数不超过两次也就是12templatesize_t Nclasslesstwobitset{public:voidset(size_t x){if(!_bt1.test(x)!_bt2.test(x))//00-01_bt2.set(x);elseif(!_bt1.test(x)_bt2.test(x)){//01-10_bt1.set(x);_bt2.reset(x);}elseif(_bt1.test(x)!_bt2.test(x))//10-11_bt2.set(x);//11不做处理 00出现0次10出现1次10出现两次,11出现3次及以上}boolis_less_two(size_t x){return(!_bt1.test(x)_bt2.test(x))||(_bt1.test(x)!_bt2.test(x));//找01,10}private:bitsetN_bt1;bitsetN_bt2;};diy::lesstwobitset10tbt;intarr[]{1,1,1,3,3,3,1,2,4,7,6,5,5};for(constinte:arr)tbt.set(e);for(size_t i0;i20;i){//直接遍历arr进行检测可能出现重复值if(tbt.is_less_two(i))coutiendl;}2.布隆过滤器也是位图的应用如果我们要确定的不是int而是字符串呢比如设置昵称时可能会看到提示该昵称已存在那么字符串-整型-映射到位图比如取模等但是会存在冲突在哈希那里就遇到过但不存在一定是准确的存在是不一定准确的比如布隆和公主殿下可能映射到一个位置因为布隆在位图中所以在检测不存在的公主殿下时结果是存在但是只要该位置为0公主殿下和布隆肯定都不存在此时不能采用拉链法来解决冲突因为位图都不存数据更不用说存个链表了我们可以不把鸡蛋放在一个篮子里比如我们可以一个字符串不止映射到一个位置可以映射到3个位置在这种情况下只有这三个位置都是1的情况下我们才认为存在只要有一个为0就是不存在set某个值的话对应的三个位置都置为1在这种情况下不在是准确的在还是不准确的但和映射一个位置相比之前一个位置被占比三个位置都被占的概率高啊所以存在的误判率可以降低可以应用于要求没那么精确的场景比如昵称是否被占就算误判存在其实也没太大影响把效率降到5%~10%但是如果误判率高客户还是不满意在这种情况下我们可以分情况处理如果是不在就是准确的返回结果如果在那可以去服务器上的数据库找一下这样可以降低服务器的负载比每一次都去服务器上找负载少多了一般服务器负载高就会比较慢负载均衡的情况下速度还可以。也是为什么称为布隆过滤器过滤掉不在的场景。牛刀小试下面关于位图说法错误的是A.位图就是用比特比特位表示一个数据的状态信息B.通过位图可以求两个集合的交集C.位图实际是哈希变形思想的一种应用D.位图可以很方便的进行字符串的映射以及查找D现有容量为10GB的磁盘分区磁盘空间以簇cluster为单位进行分配簇的大小为4KB若采用位图法管理该分区的空闲空间即用一位bit标识一个簇是否被分配则存放该位图所需簇的个数为 A.80B.320C.80KD.320KA10GB/4KB2.5*2^20b, 2.5 *2 ^20b/82.5 *2^17B5 *2^4 *4KB 80簇