[编程珠玑]-40亿数字找出一个缺失的32位整数

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

给定一个最多包含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位二分法的查找，很精妙

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