Missing Int: Given an input file with four billion non-negative integers, provide an algorithm to generate an integer that 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 MB of memory? Assume that all the values are distinct and we now have no more than one billion non-negative integers.
Hints: #235, #254, #281
解法1
一个文件里有40亿个非负整数，同时文件里的数字又没有排序，现在要写一个算法生成一个不在其中的整数。
1
2
3
4
5
6
7
|
b m t
0, 000, 000, 000
Gb Mb Kb
b: billion
m: million
t: thousand
|
注意4 billion = 4 * 1 billion = 4 * 230 = 232，而Integer的非负数最多只有231个，那也就意味着这个文件里肯定存在重复的数字。
如果我们用每个bit对应一个数字，那么需要231个bit，也就是228 bytes = 250Mb，我们现在有1GB内存，所以Hold的住。
那么算法是：
- 构建一个bit vector，里面包含231 + 1个bit
- 遍历文件，每读到一个数字在对应的bit上设置1
- 遍历bit vector，找到第一个是0的bit
- 把它变成数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public int getMissingInt(File file) {
long bits = ((long) Integer.MAX_VALUE) + 1;
byte[] bitVector = new byte[(int)(bits / Byte.SIZE)];
while (file not eof) {
String line = readLine(file);
int num = Integer.valueOf(line);
bitVector[num / Byte.SIZE] |= 1 << (num % Byte.SIZE);
}
for (int i = 0; i < bitVector.length; i++) {
int b = (int) bitVector[i];
for (int j = 0; j < Byte.SIZE; j++) {
if (b & (1 << j) == 0) {
return i * Byte.SIZE + j;
}
}
}
return -1;
}
|
解Follow Up
现在有1 Billion个不重复的非负整数，然后有10MB内存。
如果有前面bit vector的方法，我们需要250MB内存，但我们现在只有10MB，所以方法1不适合。
因为告诉你了数字不重复，那么你就可以对分段进行计数，比如分为[0, 999]、1000, 1999]，如果一个数字在某个分段范围内，那么就把这个分段的计数+1。然后当某个分段计数不等于1000的时候，就知道它里面缺少某个数字。
那么分段范围怎么确定？
每个分段都用一个Integer计数，一个Integer占用4个字节，现在有10MB内存，那么可以分为 (10 * 220) / 4 = 10 * 218 个段。
然后最多有有231个非负Integer，那么每段的大小是 231 / (10 * 218) = 213 / 10 = 8192 / 10 ~= 820。为了方便起见我们可以把分段大小变大一点，比如1024，这样会占用 < 10MB的内存。
因为知道某个段里缺少数字，那么我们就可以像前面那样用bit vector找出缺少的数字，不过这个时候的bit vector需要饱含的bit数只需要1024个就行了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
private final int SEG_SIZE = 1024;
public int getMissingInt(File file) {
int[] blocks = new int[Integer.MAX_VALUE / SEG_SIZE + 1];
while (file not eof) {
String line = readLine(file);
int n = Integer.valueOf(line);
blocks[n / SEG_SIZE]++;
}
int start = 0;
int end = 0;
for (int i = 0; i < count.length; i++) {
if (count[i] != SEG_SIZE) {
start = SEG_SIZE * i;
end = start + SEG_SIZE - 1;
break;
}
}
return findMissingInt(file, start, end);
}
private int findMissingInt(File file, int start, int end) {
byte[] bitVector = new byte[SEG_SIZE / Byte.SIZE];
while (file not eof) {
String line = readLine(file);
int n = Integer.valueOf(line);
if (n < start || n > end) {
continue;
}
bitVector[(n - start) / Byte.SIZE] |= (n - start) % Byte.SIZE;
}
for (int i = 0; i < bitVector.length; i++) {
int b = bitVector[i];
for (int j = 0; j < Byte.SIZE; j++) {
if (b & (1 << j) == 0) {
return start + i * Byte.SIZE + j;
}
}
}
return -1;
}
|
评论