[CareerCup] 10.3 Integer not Contain in the File 文件中不包含的数 - Grandyang - 博客园

[CareerCup] 10.3 Integer not Contain in the File 文件中不包含的数 - Grandyang - 博客园

[CareerCup] 10.3 Integer not Contain in the File 文件中不包含的数

 

10.3 Given an input file with four billion non-negative integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory available for this task.
FOLLOW UP
What if you have only 10 MB of memory? Assume that all the values are distinct and we now have no more than one billion non-negative integers.

 

这道题给我们了一个很大很大的数据文件，里面都是有四十亿个非负整数，现在给了我们1GB的内存大小，让我们找到一个不包括在这个文件中的非负整数，我们需要用位向量Bit Vector来做，跟之前那道5.8 Draw Horizonatal Line 画横线有些类似，题目中说数据文件总共有四十亿个数字，也就是2³²个，那么非负数就有2³¹个，给了我们1GB内存，也就是八十亿位，我们可以把每个整数都映射到内存中的不同位，逻辑如下：

1. 建立一个四十亿位大小的位向量Bit Vector，位向量是一个使用整型数组来存储bool型（或其他数据类型）值的数组，每个整型或bool型占32位。

2. 初始化位向量为0.

3. 遍历所有数字，给每个数字对应的位设为1.

4. 遍历位向量，找到第一个为0的位，算出其对应的整数。

Read full article from [CareerCup] 10.3 Integer not Contain in the File 文件中不包含的数 - Grandyang - 博客园