这道题目是编程珠玑第二章的三个问题的第一个，原题是
给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数。（在文件中至少确实一个这样的数---为什么？）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何解决该问题？
首先解释下题目中的随机排列的32位整数的顺序文件，表示的是文件写入方式是顺序写入，而文件的内容是随机排列也就是无序的40亿个32位整数
因为32位的整数总共有2^32 = 4294967296个，所以40亿个整数的文件中一定有一部分数字不在文件中。在有内存的情况下，可以通过将文件内容读入内存，排序后找到
内存充足
可以采用位图法，使用一个2^32个bit位的位图，每一位的下标表示的是相应的数字，这里会存在负数的情况。
总共需要的内存是2^32 / 8 = 536870912 字节 = 512MB
因此其实只需要512MB的内存就可以形成一个40亿多个数值的位图，然后遍历数组就可以找到不存在的数据
内存不足，借助文件的方式
首先读入每个数据，第一次，将起始位为0的写入一个文件，将起始位为1的写入一个文件，并记录两堆的数字个数，第二趟进入两堆中数字较少的一堆，如果两堆的数字个数一样，那么随机进入一堆，第二次判断第二个高位的数字又生成2堆数字，直到有一次另一堆没有出现数字，就可以判断出缺失的数字了。在数字有重复的情况下这种查询方式也一样适用
算法实现
/**
* @param n bit位数
* @param full 是否生成全部的数字
* @return
* @throws Exception
*/
public static Integer findMissNumber(int n, boolean full) throws Exception {
File f;
if (full) {
f = RandomFile.generateFull(n);
} else {
f = RandomFile.generate((int) Math.pow(2, n) > 10000 ? 10000 : (int) Math.pow(2, n) - 1);
}
String target = split(f, "", 0, n);
System.out.println(target);
if (target != null) {
if (target.length() < n) {
target = target + String.join("", Collections.nCopies(n - target.length(), "0"));
System.out.println("one target: " + target);
}
return Integer.parseInt(target,2);
} else {
return null;
}
}
/**
* @param file 读取的文件
* @param sequence 历史读取的0，1sequence
* @param index 判断从高位起的第几位bit.
* @param total 总位数
* @throws Exception
*/
public static String split(File file, String sequence, int index, int total) throws Exception {
if (index >= total) {
return null;
}
int zeroIndexCount = 0;
int oneIndexCount = 0;
File zeroFile = new File("/Users/aitozi/TMP/" + sequence + "0.txt");
File oneFile = new File("/Users/aitozi/TMP/" + sequence + "1.txt");
zeroFile.delete();
oneFile.delete();
FileOutputStream fos1 = new FileOutputStream(zeroFile);
FileOutputStream fos2 = new FileOutputStream(oneFile);
FileInputStream fis = new FileInputStream(file);
BufferedReader b = new BufferedReader(new InputStreamReader(fis));
String line;
while ((line = b.readLine()) != null) {
int value = Integer.parseInt(line);
// 从高位看起
byte bit = RandomFile.intToBits(total - 1 - index, value);
if (bit == 1) {
oneIndexCount++;
fos2.write(line.getBytes());
fos2.write("\n".getBytes());
} else {
zeroIndexCount++;
fos1.write(line.getBytes());
fos1.write("\n".getBytes());
}
}
fos1.close();
fos2.close();
if (zeroIndexCount == 0) {
return sequence + "0";
}
if (oneIndexCount == 0) {
return sequence + "1";
}
if (zeroIndexCount >= oneIndexCount) {
return split(oneFile, sequence + "1", index + 1, total);
} else {
return split(zeroFile, sequence + "0", index + 1, total);
}
}
public static void main(String[] args) throws Exception {
findMissNumber(4, true);
findMissNumber(8, true);
System.out.println(findMissNumber(8, false));
}
主要涉及的算法
- 二分搜索
- 位图法
原文其实就有提示使用二分搜索, 但是没想到是通过对每个bit位二分法的查找，很精妙
