首页 » 算法怎么学

这道题目来自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)