给定一个输入文件，包含40亿个非负整数。产生一个不在该文件中的整数。内存限制：1GB…

/**
 * 功能：给定一个输入文件，包含40亿个非负整数。产生一个不在该文件中的整数。内存限制：1GB
 * 进阶：内存限制10MB。

 */

[java] view plain copy

1. /** 
2.  * 思路： 
3.  *  
4.  * 1）创建包含40个亿个比特的位向量。 
5.  *     位向量（BV,bit vector）其实就是数组，利用整数（或另一种数据类型）数组紧凑地储存布尔值。每个整数可存储一串32比特或布尔值。 
6.  * 2）将BV的所有元素初始化为0. 
7.  * 3）扫描文件中的所有数字（num），并调用BV.set(num,1)。 
8.  * 4）接着，再次从索引0开始扫描BV。 
9.  * 5）返回第一个值为0的索引。 
10.  *  
11.  *  
12.  * 值的确定： 
13.  * 1）2^32——>40亿个不同的整数，一个整数4个字节。 
14.  * 2）2^30字节——>1GB——>2^33bit——>80亿比特位。每一位映射一个不同的整数，可以存储之多80亿个不同的整数。 
15.  */  
16. long numberOfInts=((long)Integer.MAX_VALUE)+1;  
17. byte[] bitfield=new byte[(int) (numberOfInts/8)];  
18.   
19. public void findOpenNumber() throws FileNotFoundException{  
20.     Scanner in=new Scanner(new FileReader(“f:\\file.txt”));  
21.       
22.     while(in.hasNext()){  
23.         int n=in.nextInt();  
24.         /* 
25.          *  使用OR操作符设置一个字节的第n位，找出bitfield中相对应的数字。 
26.          * （例如，10（十进制）将对应于字节数组中索引2的第2位） 
27.          */  
28.         bitfield[n/8]=(byte) (1<<(n%8));  
29.     }  
30.       
31.     for(int i=0;i<bitfield.length;i++){  
32.         for(int j=0;j<8;j++){  
33.             /* 
34.              * 取回每个字节的各个比特。当发现某个比特为0时，即找到相对应的值。 
35.              */  
36.             if((bitfield[i]&(1<<j))==0){  
37.                 System.out.println(i*8+j);  
38.                 return;  
39.             }  
40.         }  
41.     }  
42. }  

进阶：10MB

[java] view plain copy

1. /** 
2.  * 思路：对数据集进行两次扫描，就可以找出不在文件中的整数。可以将全部整数划分为同等大小的区块。 
3.  * 第一次扫描数组：确定每个数组的元素个数。 
4.  * 第二次扫描位向量：确定该范围内少的数字。 
5.  *  
6.  * bitSize::第一次扫描时每个块范围的大小。 
7.  * blockNum:第一次扫描时块的个数。 
8.  *  
9.  * 值的确定： 
10.  * 1）10MB——>2^23Byte。一个整数4个字节，因此，最多包含2^21个元素的数组。 
11.  * 2)bitSize=（2^32/blockNum）<=2^21,所以，blockNum>=2^11。 
12.  * 2^11<=bitSize<=2^26。 
13.  * 在这些条件下，挑选出越靠中间的值，那么，在任何时候所诉的内存就越少。 
14.  */  
15.   
16. int bitSize=1048576;  
17. int blockNum=4096;  
18.   
19. byte[] bitfield2=new byte[bitSize/8];  
20. int[] blocks=new int[blockNum];  
21.   
22. public void findOpenNumber2() throws FileNotFoundException{  
23.     Scanner in=new Scanner(new FileReader(“f:\\file.txt”));  
24.       
25.     int starting=-1;  
26.     while(in.hasNext()){  
27.         int n=in.nextInt();  
28.         blocks[n/bitfield2.length*8]++;  
29.     }  
30.       
31.     for(int i=0;i<blocks.length;i++){  
32.         /* 
33.          * 若小于，则说明该块中至少少了一个数字 
34.          */  
35.         if(blocks[i]<bitfield2.length*8){  
36.             starting=i*bitfield2.length*8;  
37.             break;  
38.         }  
39.     }  
40.       
41.     in =new Scanner(new FileReader(“f:\\file.txt”));  
42.     while(in.hasNext()){  
43.         int n=in.nextInt();  
44.         if(n>=starting&&n<starting+bitfield2.length*8){  
45.             bitfield2[(n-starting)/8]=(byte) (1<<((n-starting)%8));  
46.         }  
47.     }  
48.       
49.     for(int i=0;i<bitfield2.length;i++){  
50.         for(int j=0;j<8;j++){  
51.             /* 
52.              * 取回每个字节的各个比特。当发现某个比特为0时，即找到相对应的值。 
53.              */  
54.             if((bitfield2[i]&(1<<j))==0){  
55.                 System.out.println(i*8+j+starting);  
56.                 return;  
57.             }  
58.         }  
59.     }  
60.       
61. }