先看看这个题目：test.txt中有42亿个无符号整数， 求不存在于test.txt中的最小无符号整数. 限制： 可用内存为600MB.
又是大数据。 看到42亿， 有灵感没？ 要知道， 2的32次方就是42亿多一点点啊。42亿个无符号整数存在于文件里。 我们能够考虑在内存中用bit-map与之建立二值状态映射。 2的32次方个无符号整数。 须要内存空间为512M, 这个是非常easy计算的。
这么大的空间。 要用栈数组肯定不行。 可考虑用堆。
还是我们之前介绍过的bit-map, 用不着多说（别说我不描写叙述思路啊， 代码就体现了思路）， 直接给出代码：
#include <iostream>
#include <fstream>
using namespace std; #define BIT_INT 32 // 1个unsigned int能够标志32个坑
#define SHIFT 5
#define MASK 0x1f
#define N 4294967296 // 2的32次方 unsigned int *a = NULL; // 必须用堆
void createArr()
{
a = new unsigned int[1 + N / BIT_INT];
} void deleteArr()
{
delete []a;
a = NULL;
} // 将全部位都初始化为0状态
void setAllZero()
{
memset(a, 0, (1 + N / BIT_INT) * sizeof(unsigned int));
} // 设置第i位为1
void setOne(unsigned int i)
{
a[i >> SHIFT] |= (1 << (i & MASK));
} // 设置第i位为1
void setZero(unsigned int i)
{
a[i >> SHIFT] &= ~(1 << (i & MASK));
} // 检查第i位的值
int getState(unsigned int i)
{
return (a[i >> SHIFT] & (1 << (i & MASK))) && 1;
} void setStateFromFile()
{
ifstream cin("test.txt"); // 我測试的时候， 文件里的数据为：7 8 9 2 5 2 6 0 1 4
unsigned int n;
while(cin >> n)
{
setOne(n);
}
} void printResult()
{
unsigned int i = 0;
for(i = 0; i < N; i++)
{
if(0 == getState(i))
{
cout << i << endl; // 3
break;
}
}
} int main()
{
createArr();
setAllZero();
setStateFromFile();
printResult();
deleteArr(); return 0;
}
结果与预期相符。 我们在測试的时候， 用的数据较小。 有兴趣的朋友能够把数据量加大， 进行測试。
OK, 无非又是利用bit-map来节省空间而已， 事实上非常easy。
本文先介绍到这里了。