最小可用ID-----The smallest free ID problem

这篇文章上次修改于 2040 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

> 这道题目来自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
```python
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实现：
``` 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的平方

```java

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
```java
 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)

搜虎博客 - 人生天地间，忽如远行客。

最小可用ID-----The smallest free ID problem

已有 2 条评论