最小可用ID
题：在非负数组中找到最小的可分配的id(从1开始编号)，数据量1000000
思路1：开辟存储空间
private static int helper[];
public static int findID(int[] arr) {
int len = arr.length;
int[] helper = new int[len+1];
for(int i=0; i<len; i++) {
if(arr[i]<len+1) {
helper[arr[i]] = 1;
}
}
for(int i=1; i<=len; i++) {
if(helper[i]==0)
return i;
}
return len+1;
}
思路2：排序分区递归
public static int findID02(int[] arr,int l, int r) {
if(l>r)
return l+1;
int midIndex = l+((r-l)>>1); //中间数的下标
int q = select_k(arr, l,r, midIndex-l+1);
int t = midIndex+1; //期望值,该数组位置里的数本应为的值
if(q == t) {
return findID02(arr, midIndex+1, r);
}else {
return findID02(arr, l, midIndex-1);
}
}
代码参照：select_k(…)方法具体代码