下面是一道面试经典题目由上面的解题思路来看我们所学的容器能解决上述问题但是内存存不下这么大的数据,我们一般电脑的运行内存是16G而且还要运行电脑里的数据所以开这么大的空间是不可能的,位图它的原理就是:一个整型有32位byte位我么将数组中每一个下标的位置将数据转为二进制的方式就可以一个空间存32个数据所以每个二进制位的0代表该位没数据为1就是存在数据所以比如该数据为data20那就要data/32这样就知道它在哪个空间的32位整型下这里是在下标为0的32位整型下。然后再data%32就算出来在当前32位整型的第几位上这里算的是20那就是由低位到高位的第20的位置要变为1。这样就储存进去了。位图的实现库里的位图是下面这个这个位图的链接这里我们就实现 核心接口 set和reset和testset:的作用是将数据储存进去也就是在对应数据的二进制位的位置置为1reset:就是删除数据也就是在二进制位的位置置为0test :检查数据在二进制位是否存在也就是是否为1我下面插入个数据让你们直观感受可以看到下标为0的值变为了8换为二进制就是0000 1000我就不写前面那么多0了通过上面我给的计算方法也就是从0开始数第三位要变为1也是对到了下面给出框架/fonttemplatesize_t Nclassbitset{public:bitset(){_bs.resize(N/321);}private:std::vectorint_bs;};模板是可以给具体类型的参数.构造函数那里给size扩容/32是因为每个数组的位置可以存32个值嘛再加一保证不会越界set的实现voidset(size_t data){size_t idata/32;//在第几个32位整型下size_t jdata%32;//在i位置下32位整型的j位置要标记_bs[i]|(1j);}这里要用到位运算的“按位或”—— ‘|’,和左移操作符按位或就是只要有1就为1全为0才是0左移操作符就是让原数扩大两倍在二进制里的实际就是比如整数1向左移动一位就是 0001 - 0010可以看出就是将1从低位移到高位所以前面先算出在数组的第i为里的第j位,要保证其他位的不变就改变第j位的话下面给图展示更清晰如图: 按位或运算能保证只有要改变的j位置发生改变其余位置如果为1那就还是原来的1为0还是原来的0j这个位置的话因为下面的1左移j为之后的1是对到上面j的位置所以不管j这位为1还是0,最后都是1也就满足了在不改变其他位置的状态下插入数据reset的实现voidreset(size_t data){size_t idata/32;size_t jdata%32;_bs[i](~(1j));}这里要用到按位与—— 和按位取反—— ~和左移操作符按位与就是全为1就为1有0则为0.按位取反就是为1变0为0变1.要删除data也就是只改变j位置的值如图如果其他值是1因为下面除j的位置是0全为1所以其他值是1按位与之后还是1为0还是0但j位置不管是0是1都会最后变为0test的实现inttest(size_t data){size_t idata/32;size_t jdata%32;return_bs[i](1j);}这个就简单了检查j位置是不是存在按位与和左移j就行上面为1那就最后这位为1返回整数表示存在为0返回0就表示不存在所以最后我开始给的那道题的思路不就是先创造个bitset bs,然后插入数据然后bs.test(data)就行了用位图就很简单了那如果是查找出某个数出现了两次的数呢?,那就创造两个位图出现一次就01,两次10,三次以上11,也就是用我们实现的位图或者库里的位图在封装就行下面我直接给代码templatesize_t Nclasstwbitset{public:voidset(size_t data){boolf1bs1.test(data);boolf2bs2.test(data);if(!f1!f2)//00- 01{bs2.set(data);}elseif(!f1f2)// 01- 10{bs1.set(data);bs2.reset(data);}elseif(f1!f2)// 10-11{bs2.set(data);}}intgetcount(size_t data){boolf1bs1.test(data);boolf2bs2.test(data);if(!f1!f2){return0;}elseif(!f1f2){return1;}elseif(f1!f2){return2;}else{return3;}完整代码templatesize_t Nclassbitset{public:bitset(){_bs.resize(N/321);}voidset(size_t data){size_t idata/32;//在第几个32位整型下size_t jdata%32;//在i位置下32位整型的j位置要标记_bs[i]|(1j);}voidreset(size_t data){size_t idata/32;size_t jdata%32;_bs[i](~(1j));}inttest(size_t data){size_t idata/32;size_t jdata%32;return_bs[i](1j);}private:std::vectorint_bs;};