这道题目是编程珠玑第二章的三个问题的第一个，原题是

给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数。（在文件中至少确实一个这样的数—-为什么？）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何解决该问题？

首先解释下题目中的随机排列的32位整数的顺序文件，表示的是文件写入方式是顺序写入，而文件的内容是随机排列也就是无序的40亿个32位整数

因为32位的整数总共有2^32 = 4294967296个，所以40亿个整数的文件中一定有一部分数字不在文件中。在有内存的情况下，可以通过将文件内容读入内存，排序后找到

内存充足

可以采用位图法，使用一个2^32个bit位的位图，每一位的下标表示的是相应的数字，这里会存在负数的情况。
总共需要的内存是2^32 / 8 = 536870912 字节 = 512MB
因此其实只需要512MB的内存就可以形成一个40亿多个数值的位图，然后遍历数组就可以找到不存在的数据

内存不足，借助文件的方式

首先读入每个数据，第一次，将起始位为0的写入一个文件，将起始位为1的写入一个文件，并记录两堆的数字个数，第二趟进入两堆中数字较少的一堆，如果两堆的数字个数一样，那么随机进入一堆，第二次判断第二个高位的数字又生成2堆数字，直到有一次另一堆没有出现数字，就可以判断出缺失的数字了。在数字有重复的情况下这种查询方式也一样适用

算法实现

  1.   /**
  2.      * @param n bit位数
  3.      * @param full 是否生成全部的数字
  4.      * @return
  5.      * @throws Exception
  6.      */
  7.     public static Integer findMissNumber(int n, boolean full) throws Exception {
  8.         File f;
  10.         if (full) {
  11.             f = RandomFile.generateFull(n);
  12.         } else {
  13.             f = RandomFile.generate((int) Math.pow(2, n) > 10000 ? 10000 : (int) Math.pow(2, n) - 1);
  14.         }
  16.         String target = split(f, "", 0, n);
  18.         System.out.println(target);
  19.         if (target != null) {
  20.             if (target.length() < n) {
  21.                 target = target + String.join("", Collections.nCopies(n - target.length(), "0"));
  22.                 System.out.println("one target: " + target);
  23.             }
  24.             return Integer.parseInt(target,2);
  25.         } else {
  26.             return null;
  27.         }
  28.     }
  30.     /**
  31.      * @param file 读取的文件
  32.      * @param sequence 历史读取的0，1sequence
  33.      * @param index 判断从高位起的第几位bit.
  34.      * @param total 总位数
  35.      * @throws Exception
  36.      */
  37.     public static String split(File file, String sequence, int index, int total) throws Exception {
  38.         if (index >= total) {
  39.             return null;
  40.         }
  41.         int zeroIndexCount = 0;
  42.         int oneIndexCount = 0;
  43.         File zeroFile = new File("/Users/aitozi/TMP/" + sequence + "0.txt");
  44.         File oneFile = new File("/Users/aitozi/TMP/" + sequence + "1.txt");
  45.         zeroFile.delete();
  46.         oneFile.delete();
  47.         FileOutputStream fos1 = new FileOutputStream(zeroFile);
  48.         FileOutputStream fos2 = new FileOutputStream(oneFile);
  50.         FileInputStream fis = new FileInputStream(file);
  51.         BufferedReader b = new BufferedReader(new InputStreamReader(fis));
  52.         String line;
  53.         while ((line = b.readLine()) != null) {
  54.             int value = Integer.parseInt(line);
  55.             // 从高位看起
  56.             byte bit = RandomFile.intToBits(total - 1 - index, value);
  57.             if (bit == 1) {
  58.                 oneIndexCount++;
  59.                 fos2.write(line.getBytes());
  60.                 fos2.write("\n".getBytes());
  61.             } else {
  62.                 zeroIndexCount++;
  63.                 fos1.write(line.getBytes());
  64.                 fos1.write("\n".getBytes());
  65.             }
  66.         }
  67.         fos1.close();
  68.         fos2.close();
  69.         if (zeroIndexCount == 0) {
  70.             return sequence + "0";
  71.         }
  73.         if (oneIndexCount == 0) {
  74.             return sequence + "1";
  75.         }
  77.         if (zeroIndexCount >= oneIndexCount) {
  78.             return split(oneFile, sequence + "1", index + 1, total);
  79.         } else {
  80.             return split(zeroFile, sequence + "0", index + 1, total);
  81.         }
  82.     }
  84.     public static void main(String[] args) throws Exception {
  85.         findMissNumber(4, true);
  86.         findMissNumber(8, true);
  87.         System.out.println(findMissNumber(8, false));
  88.     }

主要涉及的算法

  • 二分搜索
  • 位图法

原文其实就有提示使用二分搜索, 但是没想到是通过对每个bit位二分法的查找，很精妙

其他分析
https://www.yanbinghu.com/2018/12/25/10757.html