Cracking the coding interview--Q12.3

Cracking the coding interview--Q12.3
Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory.
FOLLOW UP
What if you have only 10 MB of memory?
译文：
给你一个文件，里面包含40亿个整数，写一个算法找出该文件中不包含的一个整数， 假设你有1GB内存可用。
如果你只有10MB的内存呢？

解答

我们先来做个算术题，40亿个整数大概有多大？

40 * 10^8 * 4B = 16GB (大约值，因为不是按照2的幂来做单位换算) 

这个明显无法一次性装入内存中。但是，如果我们用计算机中的一位来表示某个数出现与否， 就可以减少内存使用量。比如在一块连续的内存区域，15出现，则将第15位置1。 这个就是Bit Map算法。关于这个算法，网上有篇文章写得挺通俗易懂的，推荐：
http://blog.csdn.net/hguisu/article/details/7880288
如果用Bit Map算法，一个整数用一位表示出现与否，需要的内存大小是：

40 * 10^8 b = 5 * 10^8 B = 0.5GB 

而我们有1GB的内存，因此该算法可行。由于Bit Map只能处理非负数， (没有说在第-1位上置1的)，因此对于有符号整数，可以将所有的数加上0x7FFFFFFF， 将数据移动到正半轴，找到一个满足条件的数再减去0x7FFFFFFF即可。 因此本文只考虑无符号整数，对于有负数的情况，按照上面的方法处理即可。
我们遍历一遍文件，将出现的数对应的那一位置1，然后遍历这些位， 找到第一个有0的位即可，这一位对应的数没有出现。代码如下：

http://blog.csdn.net/navyifanr/article/details/21296081

 public static int[] createBitMap(File file,int c) throws IOException{
  int size=c/32;
  if(c%32!=0){
   size+=1;
  }
  int[] bitmap = new int[size];
  BufferedReader reader = new BufferedReader(new FileReader(file));
  String line;
  while((line=reader.readLine())!=null){
   int number = Integer.valueOf(line);
   int idx = number/32;
   int offset = number%32;
   int i=1<<offset;
   bitmap[idx]=bitmap[idx]|i;
  }
  reader.close();
  return bitmap;
 }
 
 public static int findMissing(int[] bitmap){
  int n=0;
  for(int i=0;i<bitmap.length;i++){
   int k=1;
   for(int j=0;j<32;j++){
    if((bitmap[i]&k)!=0){
     k<<=1;
     n++;
    }else{
     return n ;
    }
   }
  }
  return  n;
 }
 public static void main(String[] args) throws IOException {
  createDataFile();
  File file = new File("1Billion.dat");
  int[] bitmap = createBitMap(file,dataSize);
  int missing=findMissing(bitmap);
  System.out.println(missing);
  
 }

    freopen("12.3.in", "r", stdin);
    
    int int_len = sizeof(int) * 8;
    int bit_len = 0xFFFFFFFF / int_len;
    int* bit = new int[bit_len];
    int v;
    while(scanf("%d", &v) != EOF){
        bit[v/int_len] |= 1<<(v%int_len);
    }
    bool found = false;
    for(int i=0; i<bit_len; ++i){
        for(int j=0; j<int_len; ++j){
            if((bit[i] & (1<<j)) == 0){
                cout<<i*int_len + j<<endl;
                found = true;
                break;
            }
                
        }
        if(found) break;
    }
    
    delete[] bit;
    fclose(stdin);

第二问，如果我们只有10MB的内存，明显使用Bit Map也无济于事了。 内存这么小，注定只能分块处理。我们可以将这么多的数据分成许多块， 比如每一个块的大小是1000，那么第一块保存的就是0到999的数，第2块保存的就是1000 到1999的数……实际上我们并不保存这些数，而是给每一个块设置一个计数器。 这样每读入一个数，我们就在它所在的块对应的计数器加1。处理结束之后， 我们找到一个块，它的计数器值小于块大小(1000)， 说明了这一段里面一定有数字是文件中所不包含的。然后我们单独处理这个块即可。
接下来我们就可以用Bit Map算法了。我们再遍历一遍数据， 把落在这个块的数对应的位置1(我们要先把这个数归约到0到blocksize之间)。 最后我们找到这个块中第一个为0的位，其对应的数就是一个没有出现在该文件中的数

    freopen("12.3.in", "r", stdin);// 20000 number
    int int_len = sizeof(int) * 8;
    int totalnum = 20000;
    int blocksize = 2000;
    int blocknum = totalnum / blocksize;
    int* block = new int[blocknum];
    int* bit = new int[blocksize/int_len+1];
    int v;
    while(scanf("%d", &v) != EOF){
        ++block[v/blocksize];
    }
    fclose(stdin);
    int start;
    for(int i=0; i<blocknum; ++i){
        if(block[i] < blocksize){
            start = i * blocksize;
            break;
        }
    }
    freopen("12.3.in", "r", stdin);
    while(scanf("%d", &v) != EOF){
        if(v>=start && v<start+blocksize){
            v -= start; // make v in [0, blocksize)
            bit[v/int_len] |= 1<<(v%int_len);
        }
    }

    bool found = false;
    for(int i=0; i<blocksize/int_len+1; ++i){
        for(int j=0; j<int_len; ++j){
            if((bit[i] & (1<<j)) == 0){
                cout<<i*int_len+j+start<<endl;
                found = true;
                break;
            }
        }
        if(found) break;
    }

    delete[] block;
    delete[] bit;
    fclose(stdin);

Read full article from Cracking the coding interview--Q12.3