dw制作一个手机网站模板下载,全屋装修设计定制整装,线上推广方式,浙江省门户网站目录 一、位图概念二、海量数据面试题 一、位图概念
假如有40亿个无重复且没有排序的无符号整数#xff0c;给一个无符号整数#xff0c;如何判断这个整数是否在这40亿个数中#xff1f;
我们用以前的思路有这些#xff1a;
把这40亿个数遍历一遍#xff0c;直到找到为… 目录 一、位图概念二、海量数据面试题 一、位图概念
假如有40亿个无重复且没有排序的无符号整数给一个无符号整数如何判断这个整数是否在这40亿个数中
我们用以前的思路有这些
把这40亿个数遍历一遍直到找到为为止排序二分查找位图解决
遍历一遍的时间复杂度为O(N)排序是O(N * logN)二分查找是O(logN)第二种还不如第一种。前面两种方法如果是针对比较小的数据的话还行。但是如果是数据很大的效率就低了。所以我们可以使用第三种方法位图解决查找数据的问题。
位图概念 位图是通过每一个比特位来判断一个数是否是在还是不在。一个二进制比特位只有两种状态要么为0要么为1如果某个数据在则对应映射的比特位为1不在对应的比特位为0。位图适用于海量数据处理且数据无重复的场景时间复杂度为O(1) 用位图解决前面的问题 有40亿个无重复且没有排序的无符号整数给一个无符号整数如何判断这个整数是否在这40亿个数中 首先要了解1G大约等于10亿个字节1个整数等于4个字节1个字节等于8个比特位。换算下40亿个整数大约是16G。但是我们不可能开出16G的内存去查找一个数用位图就可以节省很多空间了。一个整数等于32个比特位根据位图的概念用每个比特位是1还是0来确定一个数到底在不在1个整数的32个比特位可以用来确定32个数据的存在所以16G除以32等于0.5G即512M这就是开辟的空间大小是不是节省多了。
这里是我们自己模拟出来的一个简单的位图主要有以下接口
1️⃣构造 使用vector的接口resize开辟出N / 32 1的空间大小每个位置初始化为0为什么要除32因为一个整数有32个比特位这32个比特位存储在vector数组的一个位置里为什么又要加1因为假如开的空间大小是5050/32等于1那到底是一个位置还是2个位置很明显是2个第一个位置刚好满32个比特位剩余18个比特位也要有位置放因此要有第二个位置。
2️⃣将该比特位设置为1 每个数都有对应映射的比特位将这个数除以32找到该数在数组中的位置取模32找到映射的第几个比特位1左移前面取模的位数然后按位或将该比特位设置为1
3️⃣将该比特位设置为0 前面同上先按位取反1左移前面取模的位数后的数然后按位与将该比特位设置为0
4️⃣判断状态 前面同上用按位与映射的位置和1移动后的位都是1才说明这个数在 类的模板是非类型模板参数传的是数据的大小。成员变量是vector类型方便开辟空间。为什么1是左移注意左移不是真的往左边移右移也不是真的往右边移跟方向没关系。左移是往高位移动右移是往低位移动其次还要看编译器vs下是小端存储数据的所以这里是左移。 代码
namespace yss
{templatesize_t Nclass bitset{public://构造bitset(){_bit.resize(N / 32 1, 0);}//该比特位 置为1void set(size_t x){size_t i x / 32;size_t j x % 32;_bit[i] | (1 j);}//该比特位 置为0void reset(size_t x){size_t i x / 32;size_t j x % 32;_bit[i] ~(1 j);}//该比特位的状态在/不在bool test(size_t x){size_t i x / 32;size_t j x % 32;return _bit[i] (1 j);}private:vectorint _bit;};
}void Func1()
{yss::bitset100 bs;bs.set(30);bs.set(60);bs.set(90);for (size_t i 0; i 100; i){if (bs.test(i)){cout i - 在 endl;}else{cout i - 不在 endl;}}
}40亿个数据如下
yss::bitset-1* bs new bitset-1;//第一种写法
yss::bitset4294967295* bs new bitset4294967295;//第二种写法栈的空间有限对于很大的数据需要大量的内存空间应该通过堆来申请。其他同上面代码。
二、海量数据面试题 1️⃣给定100亿个整数设计算法找到只出现一次的整数 思路
使用两个位图来实现表示00(没有出现) - 01(出现一次) - 10 - 11 的情况后面两个是出现2个及2个以上本题是找到只出现一次的整数所以最终判断这个整数在不在的条件是两个位图映射的比特位是不是01有100亿个整数为了映射所有整数一个位图开辟的空间大小是512M即2的32次方个比特位两个合起来是占1G内存
代码
int main()
{vectorint a{ 2,2,3,3,5,8,8,14,14,66 };bitset-1* bs1 new bitset-1;//指针bitset-1* bs2 new bitset-1;for (auto e : a){if (bs1-test(e) false bs2-test(e) false){bs2-set(e);//00-01}else if (bs1-test(e) false bs2-test(e) true){bs1-set(e);bs2-reset(e);//01-10}else{//}}for (size_t i 0; i -1; i){if (bs1-test(i) false bs2-test(i) true){cout i endl;// 5 66}}return 0;
}2️⃣给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集 思路
既然给两个文件那么也要用两个位图。100亿个整数跟前面一样一个位图也是512M两个位图刚好1G只需判断某个数据在两个位图是否存在即可如果两个位图的对应映射的比特位都是1就是交集反之有一个不是1或者两个都是0就不是交集
代码
int main()
{vectorint a1{ 2,4,6,8,10,14,20 };vectorint a2{ 1,3,4,5,7,9,10,17 };bitset-1* bs1 new bitset-1;bitset-1* bs2 new bitset-1;for (auto e : a1){bs1-set(e);}for (auto e : a2){bs2-set(e);}for (size_t i 0; i -1; i){if (bs1-test(i) true bs2-test(i) true){cout i endl;// 4 10}}return 0;
}3️⃣1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数 思路
步骤同问题1在它的基础上增加了10-11的情况即出现3次和3次以上然后最后判断条件为出现1次和2次的数据打印出来
代码
int main()
{vectorint a{ 2,4,4,5,5,5,7,9,9,9,9 };bitset-1* bs1 new bitset-1;bitset-1* bs2 new bitset-1;for (auto e : a){if (bs1-test(e) false bs2-test(e) false){bs2-set(e);//00-01 出现1次}else if (bs1-test(e) false bs2-test(e) true){bs1-set(e);bs2-reset(e);//01-10 出现2次}else if (bs1-test(e) true bs2-test(e) false){bs2-set(e);//10-11 出现3次}//3次以上}for (size_t i 0; i -1; i){if ( (bs1-test(i) false bs2-test(i) true)|| (bs1-test(i) true bs2-test(i) false)){cout i endl;// 2 4 7}}return 0;
}
