大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
题目: 给40个亿不重复的无符号整数,没有排序过,随机给出一个无符号整数,快速的判断这个数在或者不在40亿个数中?
1. 思路
2. 代码实现
#include "stdio.h" // 用位图的方式实现大数据的查找 #include <vector> #include <iostream> using namespace std; class CBitmapFind { enum{INFOBITS_IN_VECT = 8}; public: // 确定容器大小 explicit CBitmapFind(size_t nRange = 0) { BitmapVect.resize(nRange / INFOBITS_IN_VECT + 1); } // 添加单个元素并标记该元素 void AddElement(int nNum) { // 确定该数据所在vect中的位置 int nVectIndex = nNum / INFOBITS_IN_VECT; // 确定在vect索引中的byte位置 int nByteIndex = nNum % 8; BitmapVect[nVectIndex] |= (1 << nByteIndex); } // 删除单个元素并移除单个元素 void MoveElement(int nNum) { // 确定该数据所在vect中的位置 int nVectIndex = nNum / INFOBITS_IN_VECT; // 确定在vect索引中的byte位置 int nByteIndex = nNum % 8; BitmapVect[nVectIndex] &= ~(1 << nByteIndex); } bool TestBit(int nNum) { // 确定该数据所在vect中的位置 int nVectIndex = nNum / INFOBITS_IN_VECT; // 确定在vect索引中的byte位置 int nByteIndex = nNum % 8; return (BitmapVect[nVectIndex] & (1 << nByteIndex)? true:false); } private: vector<char> BitmapVect; };
3. 扩展:判断出现是次数是否大于3
// 用位图的方式实现大数据的查找,判断出现的次数,下面的代码只能处理出现次数小于等于3的情况 // 00 01 10 11 class CNBitmapFind { public: enum{ INFOBITS_IN_VECT = 4 }; // 确定容器大小 explicit CNBitmapFind(size_t nRange = 0) { BitmapVect.resize(nRange / INFOBITS_IN_VECT + 1); } // 添加单个元素并标记该元素出现的次数 void AddElement(int nNum) { // 确定该数据所在vect中的位置 int nVectIndex = nNum / INFOBITS_IN_VECT; // 确定元素在vect索引中的byte位置 int nByteIndex = nNum % INFOBITS_IN_VECT; nByteIndex *= 2; bool first = BitmapVect[nVectIndex] & (1 << nByteIndex); bool second = BitmapVect[nVectIndex] & (1 << (nByteIndex + 1)); if (!(first && second)) { BitmapVect[nVectIndex] += (1 << nByteIndex); } } int Test(int nNum) { // 确定该数据所在vect中的位置 int nVectIndex = nNum / INFOBITS_IN_VECT; // 确定元素在vect索引中的byte位置 int nByteIndex = nNum % INFOBITS_IN_VECT; nByteIndex *= 2; int first = BitmapVect[nVectIndex] & (1 << nByteIndex)?1:0; int second = BitmapVect[nVectIndex] & (1 << (nByteIndex + 1))?1:0; return second * 2 + first; } private: vector<char> BitmapVect; };
4. 测试
void main() { int nReange = 4 * pow(10, 2); CBitmapFind BitmapFind(nReange); for (int i = 0; i < nReange; i++) { BitmapFind.AddElement(i); } cout << "CBitmapFind测试:" << endl; BitmapFind.TestBit(401) ? (cout << "找到:" << 401 << endl) : (cout << "未找到" << 401 << endl); BitmapFind.TestBit(388) ? (cout << "找到" << 388 << endl) : (cout << "未找到" << 388 << endl); CNBitmapFind NBitmapFind(6); NBitmapFind.AddElement(1); NBitmapFind.AddElement(1); NBitmapFind.AddElement(1); NBitmapFind.AddElement(2); NBitmapFind.AddElement(2); NBitmapFind.AddElement(3); cout << "CNBitmapFind测试:" << endl; cout << "1出现的次数:" << NBitmapFind.Test(1) << endl; cout << "2出现的次数:" << NBitmapFind.Test(2) << endl; cout << "3出现的次数:" << NBitmapFind.Test(3) << endl; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120125.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...