大家好，又见面了，我是全栈君。
/**
* 功能：给定一个输入文件，包含40亿个非负整数。产生一个不在该文件中的整数。内存限制：1GB
* 进阶：内存限制10MB。
*/
[java] view plain copy
- /**
- * 思路：
- *
- * 1）创建包含40个亿个比特的位向量。
- * 位向量（BV,bit vector）其实就是数组，利用整数（或另一种数据类型）数组紧凑地储存布尔值。每个整数可存储一串32比特或布尔值。
- * 2）将BV的所有元素初始化为0.
- * 3）扫描文件中的所有数字（num），并调用BV.set(num,1)。
- * 4）接着，再次从索引0开始扫描BV。
- * 5）返回第一个值为0的索引。
- *
- *
- * 值的确定：
- * 1）2^32——>40亿个不同的整数，一个整数4个字节。
- * 2）2^30字节——>1GB——>2^33bit——>80亿比特位。每一位映射一个不同的整数，可以存储之多80亿个不同的整数。
- */
- long numberOfInts=((long)Integer.MAX_VALUE)+1;
- byte[] bitfield=new byte[(int) (numberOfInts/8)];
- public void findOpenNumber() throws FileNotFoundException{
- Scanner in=new Scanner(new FileReader(“f:\\file.txt”));
- while(in.hasNext()){
- int n=in.nextInt();
- /*
- * 使用OR操作符设置一个字节的第n位，找出bitfield中相对应的数字。
- * （例如，10（十进制）将对应于字节数组中索引2的第2位）
- */
- bitfield[n/8]=(byte) (1<<(n%8));
- }
- for(int i=0;i<bitfield.length;i++){
- for(int j=0;j<8;j++){
- /*
- * 取回每个字节的各个比特。当发现某个比特为0时，即找到相对应的值。
- */
- if((bitfield[i]&(1<<j))==0){
- System.out.println(i*8+j);
- return;
- }
- }
- }
- }
进阶：10MB
[java] view plain copy
- /**
- * 思路：对数据集进行两次扫描，就可以找出不在文件中的整数。可以将全部整数划分为同等大小的区块。
- * 第一次扫描数组：确定每个数组的元素个数。
- * 第二次扫描位向量：确定该范围内少的数字。
- *
- * bitSize::第一次扫描时每个块范围的大小。
- * blockNum:第一次扫描时块的个数。
- *
- * 值的确定：
- * 1）10MB——>2^23Byte。一个整数4个字节，因此，最多包含2^21个元素的数组。
- * 2)bitSize=（2^32/blockNum）<=2^21,所以，blockNum>=2^11。
- * 2^11<=bitSize<=2^26。
- * 在这些条件下，挑选出越靠中间的值，那么，在任何时候所诉的内存就越少。
- */
- int bitSize=1048576;
- int blockNum=4096;
- byte[] bitfield2=new byte[bitSize/8];
- int[] blocks=new int[blockNum];
- public void findOpenNumber2() throws FileNotFoundException{
- Scanner in=new Scanner(new FileReader(“f:\\file.txt”));
- int starting=-1;
- while(in.hasNext()){
- int n=in.nextInt();
- blocks[n/bitfield2.length*8]++;
- }
- for(int i=0;i<blocks.length;i++){
- /*
- * 若小于，则说明该块中至少少了一个数字
- */
- if(blocks[i]<bitfield2.length*8){
- starting=i*bitfield2.length*8;
- break;
- }
- }
- in =new Scanner(new FileReader(“f:\\file.txt”));
- while(in.hasNext()){
- int n=in.nextInt();
- if(n>=starting&&n<starting+bitfield2.length*8){
- bitfield2[(n-starting)/8]=(byte) (1<<((n-starting)%8));
- }
- }
- for(int i=0;i<bitfield2.length;i++){
- for(int j=0;j<8;j++){
- /*
- * 取回每个字节的各个比特。当发现某个比特为0时，即找到相对应的值。
- */
- if((bitfield2[i]&(1<<j))==0){
- System.out.println(i*8+j+starting);
- return;
- }
- }
- }
- }
转载于:https://my.oschina.net/u/2822116/blog/792607
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/108766.html原文链接：https://javaforall.net
