模板网站有什么不好,自己做图网站,大连网站如何制作,类似开发次元世界文章目录 引入1.位图的介绍1.1位图的概念1.2位图的应用1.3bitset的基本使用bitset的定义方式bitset成员函数的使用 2.位图的基本模拟实现2.1基本结构2.2构造函数2.3set函数2.4reset2.5test 3.位图考察题目3.1只出现⼀次的整数#xff1f;3.2找到两个文件交集#xff1f;3.3出… 文章目录 引入1.位图的介绍1.1位图的概念1.2位图的应用1.3bitset的基本使用bitset的定义方式bitset成员函数的使用 2.位图的基本模拟实现2.1基本结构2.2构造函数2.3set函数2.4reset2.5test 3.位图考察题目3.1只出现⼀次的整数3.2找到两个文件交集3.3出现次数不超过2次的所有整数(出现1次和2次) 总结 引入
给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中
要判断一个数是否在某一堆数中我们可能会想到如下方法
将这一堆数进行排序然后通过二分查找的方法判断该数是否在这一堆数中。将这一堆数插入到unordered_set容器中然后调用find函数判断该数是否在这一堆数中。 单从方法上来看这两种方法都是可以而且效率也不错第一种方法的时间复杂度是O(NlogN)第二种方法的时间复杂度是O(N)。
但问题是这里有40亿个数若是我们要将这些数全部加载到内存当中那么将会占用16G的空间空间消耗是很大的。因此从空间消耗来看上面这两种方法实际都是不可行的。
1.位图的介绍 实际在这个问题当中我们只需要判断一个数在或是不在即只有两种状态那么我们可以用一个比特位来表示数据是否存在如果比特位为1则表示存在比特位为0则表示不存在。 无符号整数总共有232个因此记录这些数字就需要232个比特位也就是512M的内存空间内存消耗大大减少。
1.1位图的概念
所谓位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常是用来判断某个数据存不存在的。
1.2位图的应用
常见位图的应用如下
1. 快速查找某个数据是否在一个集合中。
2. 排序。
3. 求两个集合的交集、并集等。
4. 操作系统中磁盘块标记。
5. 内核中信号标志位信号屏蔽字和未决信号集。1.3bitset的基本使用
bitset的定义方式
方式一 构造一个16位的位图所有位都初始化为0。
bitset16 bs1; //0000000000000000方式二 构造一个16位的位图根据所给值初始化位图的前n位。
bitset16 bs2(0xfa5); //0000111110100101方式三 构造一个16位的位图根据字符串中的0/1序列初始化位图的前n位。
bitset16 bs3(string(10111001)); //0000000010111001bitset成员函数的使用
bitset中常用的成员函数如下
成员函数功能set设置指定位或所有位reset清空指定位或所有位flip反转指定位或所有位test获取指定位的状态count获取被设置位的个数size获取可以容纳的位的个数any如果有任何一个位被设置则返回truenone如果没有位被设置则返回trueall如果所有位都被设置则返回true
具体用法可以用的时候再查询文档 bitset使用文档
2.位图的基本模拟实现
2.1基本结构
templatesize_t N
class bitset
{
public:// 构造函数bitset();// x映射的位标记成1void set(size_t x);// x映射的位标记成0void reset(size_t x);// x映射的位是1返回真0返回假bool test(size_t x);
private:vectorint _bs;
};2.2构造函数
在构造位图时我们需要根据所给位数N创建一个N位的位图并且将该位图中的所有位都初始化为0。
一个整型有32个比特位因此N个位的位图就需要用到N/32个整型但是实际我们所需的整型个数是N/321因为所给非类型模板参数N的值可能并不是32的整数倍。
例如当N为40时我们需要用到两个整型即40/3212。 bitset()
{// 扩容不管能否整除都多开一个空间_bs.resize(N / 32 1);
}2.3set函数
设置位图中指定的位的方法如下
计算出该位位于第 i 个整数的第 j 个比特位。 将1左移 j 位后与第 i 个整数进行或运算即可。
// x映射的位标记成1
void set(size_t x)
{size_t i x / 32;size_t j x % 32;_bs[i] | (1 j);
}2.4reset
清空位图中指定的位的方法如下
计算出该位位于第 i 个整数的第 j 个比特位。 将1左移 j 位再整体反转后与第 i 个整数进行与运算即可。
// x映射的位标记成0
void reset(size_t x)
{size_t i x / 32;size_t j x % 32;_bs[i] (~(1 j));
}2.5test
获取位图中指定的位的状态的方法如下
计算出该位位于第 i 个整数的第 j 个比特位。 将1左移 j 位后与第 i 个整数进行与运算得出结果。 若结果非0则该位被设置否则该位未被设置。 // x映射的位是1返回真0返回假
bool test(size_t x)
{size_t i x / 32;size_t j x % 32;return _bs[i] (1 j);
}3.位图考察题目
给定100亿个整数设计算法找到只出现⼀次的整数 虽然是100亿个数但是还是按范围开空间所以还是开2^32个位跟前面的题目是⼀样的。给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集 把数据读出来分别放到两个位图依次遍历同时在两个位图的值就是交集⼀个文件有100亿个整数1G内存设计算法找到出现次数不超过2次的所有整数
根据上面的题意我们需要通过位图实现一个能表示出现0次1次2次多次的位图因此可以实现一个两个位图成员的类。
namespace twobt
{templatesize_t Nclass twobitset{public:void set(size_t x){bool bit1 _bs1.test(x);bool bit2 _bs2.test(x);if (!bit1 !bit2) // 00-01{_bs2.set(x);}else if (!bit1 bit2) // 01-10{_bs1.set(x);_bs2.reset(x);}else if (bit1 !bit2) // 10-11{_bs1.set(x);_bs2.set(x);}}// 返回0 出现0次数// 返回1 出现1次数// 返回2 出现2次数// 返回3 出现2次及以上int get_count(size_t x){bool bit1 _bs1.test(x);bool bit2 _bs2.test(x);if (!bit1 !bit2){return 0;}else if (!bit1 bit2){return 1;}else if (bit1 !bit2){return 2;}else{return 3;}}private:bitsetN _bs1;bitsetN _bs2;};
}3.1只出现⼀次的整数
代码演示:
void test_twobitset1()
{lin::twobitset100 tbs;int a[] { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6,6,6,6,7,9 };for (auto e : a){tbs.set(e);}// 只出现一次的整数for (size_t i 0; i 100; i){if (tbs.get_count(i) 1){cout i endl;}}
}3.2找到两个文件交集
代码演示
void test_bitset()
{int a1[] { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };int a2[] { 5,3,5,99,6,99,33,66 };bitset100 bs1;bitset100 bs2;for (auto e : a1){bs1.set(e);}for (auto e : a2){bs2.set(e);}// 两个文件的交集for (size_t i 0; i 100; i){// 第i的位置都是1就是交集if (bs1.test(i) bs2.test(i)){cout i endl;}}
}3.3出现次数不超过2次的所有整数(出现1次和2次)
代码演示
void test_twobitset2()
{lin::twobitset100 tbs;int a[] { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6,6,6,6,7,9 };for (auto e : a){tbs.set(e);}// 出现次数不超过2次的所有整数for (size_t i 0; i 100; i){//cout i - tbs.get_count(i) endl;if (tbs.get_count(i) 1 || tbs.get_count(i) 2){cout i endl;}}
}总结
位图的优缺点 优点增删查改快节省空间 缺点只适用于整形 本篇博客到此结束欢迎各位评论区留言~
