找到一个不在40亿给定的整数中
这是一个采访问题：
给定一个有40亿个整数的输入文件，提供一个算法来生成一个不包含在文件中的整数。 假设你有1 GB的内存。 如果您只有10 MB内存，请跟进您的操作。
我的分析：
文件大小为4×109×4字节= 16 GB。
我们可以进行外部排序，因此我们可以了解整数的范围。 我的问题是什么是检测排序的大整数集中丢失的整数的最佳方法？
我的理解（阅读所有答案后）：
假设我们正在谈论32位整数。 有2 ^ 32 = 4 * 109个不同的整数。
情况1：我们有1 GB = 1 * 109 * 8位= 80亿位内存。 解决方案：如果我们使用一位代表一个不同的整数，这就足够了。 我们不需要排序。 执行：
int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
Scanner in = new Scanner(new FileReader("a.txt"));
while(in.hasNextInt()){
int n = in.nextInt();
bitfield[n/radix] |= (1 << (n%radix));
}
for(int i = 0; i< bitfield.lenght; i++){
for(int j =0; j<radix; j++){
if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
}
}
}
情况2：10MB存储器= 10×106×8位= 8000万位
Solution: For all possible 16-bit prefixes, there are 2^16 number of
integers = 65536, we need 2^16 * 4 * 8 = 2 million bits. We need build
65536 buckets. For each bucket, we need 4 bytes holding all possibilities because
the worst case is all the 4 billion integers belong to the same bucket.
step1: Build the counter of each bucket through the first pass through the file.
step2: Scan the buckets, find the first one who has less than 65536 hit.
step3: Build new buckets whose high 16-bit prefixes are we found in step2
through second pass of the file
step4: Scan the buckets built in step3, find the first bucket which doesnt
have a hit.
The code is very similar to above one.
结论：我们通过增加文件传递来减少内存。
对迟到者的澄清：正如问到的那样，问题并不是说文件中只包含一个整数，至少这不是大多数人解释它的方式。 不过，评论主题中的许多评论都是关于该任务的变化。 不幸的是， 将它引入到评论主题的评论后来被其作者删除，所以现在看起来孤儿回复只是误解了所有内容。 这很混乱。 抱歉。
假设“整数”意味着32位 ：拥有10 MB的空间足以让您计算输入文件中具有任何给定的16位前缀的数量，对于所有可能的16位前缀输入文件。 至少有一个水桶的命中次数不会超过2 ^ 16次。 再次查找该桶中哪些可能的数字已被使用。
如果它意味着多于32位，但仍然是有限大小 ：如上所述，忽略发生在（有符号或无符号;您的选择）32位范围之外的所有输入数字。
如果“整数”表示数学整数 ：读取一次输入并跟踪您见过的最长号码的最大号码长度。 完成后，输出最大加一个随机数，再加一个数字。 （文件中的其中一个数字可能是一个需要超过10 MB来表示的bignum，但是如果输入是文件，那么您至少可以表示适合它的任何东西的长度）。
统计通知的算法使用少于确定性方法的通过来解决此问题。
如果允许非常大的整数，那么可以生成一个在O（1）时间内可能唯一的数字。 像一个GUID这样的伪随机128位整数只会在每个640亿亿个案例中不到一个与现有的40亿个整数中的一个相冲突。
如果整数被限制为32位，那么可以使用小于10 MB的单次传输生成一个可能唯一的数字。 伪随机32位整数将与40亿现有整数中的一个相冲突的几率约为93％（4e9 / 2 ^ 32）。 1000个伪随机整数将全部相撞的概率小于12,000亿十亿的一个概率（单次碰撞的概率^ 1000）。 因此，如果一个程序维护一个包含1000个伪随机候选的数据结构，并遍历已知整数，从候选中消除匹配，那么至少可以找到一个不在文件中的整数。
关于这个问题的详细讨论已经在Jon Bentley的“第一章开裂的牡蛎”编程珍珠Addison-Wesley pp.3-10
Bentley讨论了几种方法，包括外部排序，使用多个外部文件的合并排序等，但Bentley提出的最佳方法是使用位域的单通道算法，他幽默地称之为“奇迹排序”:)回答这个问题，有40亿数字可以表示为：
4 billion bits = (4000000000 / 8) bytes = about 0.466 GB
实现bitset的代码很简单:(从解决方案页面获取）
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }
Bentley算法对文件进行一次遍历， set阵列中的适当位，然后使用上面的test宏来检查该阵列以找到缺失的数字。
如果可用内存小于0.466 GB，则Bentley建议使用k-pass算法，该算法根据可用内存将输入分为多个范围。 举一个非常简单的例子，如果只有1个字节（即处理8个数字的内存）可用，范围从0到31，我们将它分成0到7,8-15,16-22等范围，等等并在每个32/8 = 4遍中处理这个范围。
HTH。
链接地址: http://www.djcxy.com/p/12217.html