Find an integer not among four billion given ones
Given an input file with four billion non-negative integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory available for this task.
Follow Up
What if you have only 10 M8 of memory? Assume that all the values are distinct and we now have no more than one billion non-negative integers.
解题思路
总共有2^32（或40亿-->4 billion）个不同的整数。我们有1G内存，相当于有80亿个bits。
有80亿个bits，就可以把所有可能的整数映射到一个不同的bit：
- 创建一个有40亿的Bit Vector。
- 把Bit Vector初始化为0.
- 从文件中扫描所有整数，把对应的Bit Vector设置为1.
- 从索引0开始扫描Bit Vector。
- 返回值为0的第一个索引值。
long numberOflnts = ((long) Integer.MAX_VALUE) + I;
byte[] bitfield = new byte [(int) (numberOflnts / 8)];
void findOpenNumber()throws FileNotFoundException {
Scanner in = new Scanner(new FileReader("file.txt"));
while (in.hasNextInt()) {
int n = in.nextlnt ();
/* Finds the corresponding number in the bitfield by using
* the OR operator to set the nth bit of a byte
* (e.g., 10 would correspond to the 2nd bit of index 2 in
* the byte array). */
bitfield [n / 8] |= 1 << (n % 8);
}
for (int i = 0; i < bitfield.length; i++) {
for (int j = 0; j < 8; j++) {
/* Retrieves the individual bits of each byte. When 0 bit
* is found, finds the corresponding value. */
if ((bitfield[i] & (1 << j)) == 0) {
System.out.println (i * 8 + j);
return;
}
}
}
}
如果只有10MB内存怎么办？
可能会通过对数据集扫描2次来发现missing数字。将整数划分正适度大小的块（后面将讨论如何决定块的大小）。假设将所有整数划分成1000块，那么块0表示0---999整数集合，块1表示1000---1999的整数集合,等等。
因为没有重复值，因而我们知道每个块应该包含多少个值，在我们搜索文件的时候，计算在0---999区间包含多少值，在1000---1999区间包含多少值，等等。如果在某个特定的区间内只有999个值，我们就知道缺失的数字就一定在这个区间内。
在第二遍扫描时，就找那个特定区间内缺失的数字，还是使用bit vector 方式，可以忽略任何不在这个区间范围内的数字。
现在的问题是我们如何决定块的大小？让我们定义一些变量
- rangeSize表示第一遍扫描时每个块的大小
- arraySize表示第一遍扫描时块的数目,因为有2^31个非负整数，所以arraySize = 2^31/rangeSize
我们需要为rangeSize选择一个值，让第一遍扫描(数组)和第二遍扫描(bit vector)都有足够的内存。
第一遍:确定块的大小
10MB内存大致相当于2^23个字节，因为数组元素是int，一个int需要4个字节， 因而数组最多包含的元素个数是2^21，可以得到下面的公式：
- arraySize = 2^31/rangeSize
- rangeSize >=2^31/2^21
- rangeSize >=2^10
第二遍：bit vector
需要足够的空间存储rangeSize位(bit)。2^23字节的内存空间可以存储2^26位。 因而，我们可以得到下面的公式：
2^10<=rangeSize<=2^26
这些条件给了我们足够大的"摇摆空间"，但在任何时候，越靠近中间用的内存越少。
int bitsize = 1048576; // 2^20 bits (2^17 bytes)
int blockNum = 4096; // 2^12
byte[] bitfield = new byte[bitsize/8];
int[] blocks = new int [blockNum];
void findOpenNumber() throws FileNotFoundException {
int starting = -l;
Scanner in = new Scanner (new FileReader ("file.txt"));
//计算每块包含的元素数目
while (in.hasNextlntO) {
int n = in.nextInt();
blocks[n / (bitfield.length * 8)]++;
}
for (int i = 0; i < blocks. length; i++) {
if (blocks[i] < bitfield.length * 8){
//如果某个块的元素数目小于2^20,这个快至少存在一个缺失的数字
starting = i * bitfield.length * 8;
break;
}
}
Scanner in = new Scanner (new FileReader ("file.txt"));
while (in.hasNextInt()) {
int n = in.nextInt();
//如果某个数字属于缺失数字的块，记录这个数字
if (n >= starting && n < starting + bitfield.length * 8) {
bitfield[(n-starting) / 8] |= 1 << ((n - starting) % 8);
}
}
for (int i = 0 ; i < bitfield.length; i++) {
for (int j = 0; j < 8; j++) {
//获取每个字节的单个bit，当方向某个bit为0时，就找到了对应的值
if ((bitfield[i] & (1 << j)) == 0) {
System.out.println(i * 8 + j + starting);
return;
}
}
}
}