文章目录
- 前言
- 一、 bitset模拟实现
- 二、 常见面试题
- 1.给你一百亿个整数，找到只出现一次的数字
- 2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
前言
- 快速查找某个数据是否在一个集合中
- 排序 + 去重
- 求两个集合的交集、并集等
- 操作系统中磁盘块标记
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：
一、 bitset模拟实现
namespace bit {template<size_t N>//非类型模板参数//N为我们要开的多少个比特位class bitset {public:bitset(){//我们用int类型来模拟，一个int一共32个比特_a.resize(N / 32 + 1);}void set(size_t x) {//将对应比特位变为1int i = x / 32;//i为在第几个int中int j = x % 32;//j为在这个int的32个比特位的哪个位置_a[i] |= (1 << j);//按位或：：只有双方对应位置都是0的时候才为0}void reset(size_t x) {//将对应比特位变为0int i = x / 32;int j = x % 32;_a[i] &= (~(1 << j));//按位与：：只有双方对应位置都是1的时候才为1//左移后按位取反，相当于除了j位置为0其他位置都为1，按位与的时候其他位//不受影响}bool test(size_t x) {//判断这个位置存不存在int i = x / 32;int j = x % 32;//这里按位与并没有改变原来值的大小，//因为返回的是一个临时变量return _a[i] & (1 << j);}private:vector<int> _a;};
二、 常见面试题
1.给你一百亿个整数，找到只出现一次的数字
我们可以使用两个位图，两个位图所组成的两位的二进制，用来表示出现次数，我们只需对两个表中的存在情况进行讨论就能确定他们出现此处，找出所有标记位01的数
00出现0次，01出现1次，10出现两次，11出现两次以上
template<size_t N>class twobitset{public:void set(size_t x){//00出现0次，01出现1次，10出现两次，11出现两次以上// 00 -> 01if (!_bs1.test(x) && !_bs2.test(x)){_bs2.set(x);} // 01 -> 10else if (!_bs1.test(x) && _bs2.test(x)){_bs1.set(x);_bs2.reset(x);}// 本身10代表出现2次及以上，就不变了}bool is_once(size_t x){return !_bs1.test(x) && _bs2.test(x);}private:bitset<N> _bs1;bitset<N> _bs2;};
2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
两个文件分别放到位图里面，然后判断两个位图的相同位置值是否相同。
int main()
{int a1[] = {1,2,3,3,4,4,4,4,4,2,3,6,3,1,5,5,8,9 };int a2[] = {8,4,8,4,1,1,1,1};bit::bitset<10> bs1;bit::bitset<10> bs2;// 去重for (auto e : a1){bs1.set(e);}// 去重for (auto e : a2){bs2.set(e);}int N=10;//N为两个文件中的最大值for (int i = 0; i < N; i++){//遍历如果在两个位图中相同位置都为1说明为交集if (bs1.test(i) && bs2.test(i)){cout << i << " ";}}cout << endl;
}
