这道题目来自Richard Bird书中的第一章[1]。现代社会中,有很多服务依赖一种被称为ID的概念。例如身份证就是一种ID,银行账户也是一种ID,电话号码本质上也是一种ID。假设我们使用非负整数作为某个系统的的ID,所有用户都由一个ID唯一确定。任何时间,这个系统中有些ID处在使用中的状态,有些ID则可以用于分配给新用户。现在的问题是,怎样才能找到最小的可分配ID呢?例
如下面的列表记录了当前正在被使用的ID:

[18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6] ---后面称数组A

[1] 暴力实现： brute force---python，从0开始找到第一个不在list内的整数ID

lst = [18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6]
i = 0
while True:
  if i not in lst:
    print i
    break
  i = i + 1

复杂度分析：可以看出这个算法是2维的，就是在遍历i到n的是一维，然后在一维空间再便利是否在list中，对于这种算法，有个简单的复杂度BigO总结：O（n2),即n的平方
[2]空间换时间实现：这里基于一个事实---这个数组A的长度为15，那么1-16这个取值区间的整数一定有一个最小可用ID，否则，数组里面的数字一定是1，2,3，4,5，6...11,12,13,14,15这样的数组。基于这个事实，我们可以初始化一个长度为16的Bool数组B，默认值为false，然后遍历数组A，如果A的值小于16，比如是8，则把数组B中的B[8]标记为True。最后，我们遍历数组B，找到第一个为False的即为最小可用ID。java实现：

    int[] listA = {18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6};
    int blength = listA.length + 1;//加1是利用如果找不到，n+1 就是最小可用ID
    boolean[] listB = new boolean[blength];
    for(int i =0; i< listB.length;i++){
      listB[i] = false;
    }
    for(int j =0;j < listA.length;j++ ){
      if(listA[j] < blength ){
        int a = listA[j];
        listB[a] = true;
      }
    }
    for(int k =0;k < listB.length;k++){
      if(false == listB[k]){
        System.out.print(k);
        break;
      }
    }

进一步优化，使用bit位运算，进一步节省空间和计算步骤,java代码：注意最后一个for不是在上面的for的维度里面，所以不能算n的平方

     int[] listA = {18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6};
         var intSize = Integer.BYTES*8;
         var lenghB = (listA.length + 1)/intSize +1;
         int[] listBit = new int[lenghB];
         
         for(var i = 0;i < listA.length;i ++) {
             var v = listA[i];
             listBit[v / intSize] |= 1 << (v%intSize);//把该位变成1
         }
         for(var j = 0;j < listBit.length;j ++) {
             int v = listBit[j];
             int vv = ~v;//取反
             if(vv ==0) {
                 continue;
             }
            
             for(var k =0;k < intSize ;k++) {//注意这个for不是在上面的for的维度里面，所以不能算n的平方
                 var testKv = 1 <<k;
                 if((testKv & v) ==0) {
                     System.out.print(intSize*j+k);
                     break;
                 }
             }
            
         }

复杂度分析：这个算法随着N的增长是线性的，所以复杂度为O(n)

[3]分治思想division，分治是个很巧妙的思想。首先是分。把一个问题分成N份，然后锁定问题到其中的1/N，然后对1/N再分，缩小为1/N/N;然后是治：当问题已经缩小为不能再分时，分析里面的数字就可以得出结论。这也是为什么分治的复杂度一般为logN，即除以N多少次变成1。比如常见的二分查找。
java代码如下,注意治的最后落点和没有分的时候的落点一样，就是找最后一个元素的下一个id

 int[] listA =  {18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6};
 int arrayStart = 0;
 int arrayEnd = listA.length -1;
 int left =0;
 while(arrayEnd >= arrayStart) {//最后剩余1个元素，也要和middlenum比较
     left = arrayStart;
     int right ;
     int middleNum = (arrayEnd+arrayStart)/2  ;//数组长度的中间值
     for(right = arrayStart; right <= arrayEnd;right++  ) {
         if(listA[right] <= middleNum) {
             //交换
             int temp = listA[left];
             listA[left] = listA[right];
             listA[right] = temp;
             left++;
         }
     }
     //分的思想
     if(left == middleNum +1) {//表示左边的表已经满了，最小ID还在右边,start 就是left,end 不变
        
        arrayStart = left;

     }else {//ID在左边,start不变,end 变成left-1
        arrayEnd = left -1;
     }
     
     
 }
 System.out.print(left);//最小可用ID的xia一个ID，+1,就是最小ID

复杂度分析，外部循环只是内部循环的重入条件，复杂度是O(n + n/2 + n/4 + ...) = O(2n) = O(n)