相关疑难解决方法(0)

这是一个面试问题:

给定一个包含40亿个整数的输入文件,提供一个算法来生成一个未包含在文件中的整数.假设您有1 GB内存.如果您只有10 MB内存,请跟进您的操作.

我的分析:

文件大小为4×10 ⁹ ×4字节= 16 GB.

我们可以进行外部排序,因此我们可以了解整数的范围.我的问题是在排序的大整数集中检测缺失整数的最佳方法是什么？

我的理解(阅读完所有答案后):

假设我们正在讨论32位整数.有2 ^ 32 = 4*10 ^9个不同的整数.

情况1:我们有1 GB = 1*10 ⁹*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:10 MB内存= …

这是描述的问题Programming pearls.我无法理解作者所描述的二进制搜索方法.任何人都可以帮忙详细说明吗？谢谢.

编辑:我一般可以理解二进制搜索.我只是无法理解如何在这种特殊情况下应用二进制搜索.如何确定缺失的数字是否在某个范围内,以便我们可以选择另一个.英语不是我的母语,这是我无法理解作者的一个原因.所以,请使用普通英语:)

编辑:谢谢大家的好评和评论!我从解决这个问题中学到的最重要的一课就是二元搜索不仅适用于排序数组!