java常用算法,给个int数组,数字不连续,找出最小空缺数

Question

比如一个数组 int[] arrays = new int[]{1,2,3,6,10};
能正确返回4,注意整形数组比较大,10w数量级,

Answer 1

public static void main(String[] args) {

int[] array = new int[] {1,2,3,6,7,8,9,10,11,12, 13, 14, 15, 16, 17, 18, 19, 20 };
//将数组拆分
int minque = 1;
if (1 == array[0]){
minque = zhaoque(array);
}
System.out.println(minque);
}

public static int zhaoque(int[] array){
int minque = 1;
//array 不为空
if (null != array && array.length>0){
if (array.length == 1){
minque = array[0]+1;
} else if(array.length == 2){
if (1 == (array[1] - array[0])){
minque = array[1]+1;
} else {
minque = array[0]+1;
}
} else {
int headlength = (array.length+1)/2;
int[] headArray = new int[headlength];
System.arraycopy(array,0,headArray,0,headlength);
//检查前半部分是否密集
int headmin = headArray[0];
int headmax = headArray[headlength-1];
if (headlength > (headmax - headmin)){
//前部分密集分布
int footlength = array.length - headlength;
int[] footArray = new int[footlength];
System.arraycopy(array,headlength,footArray,0,footlength);
int footmin = footArray[0];
int footmax = footArray[footlength-1];
// 检查后部分是否与前部分衔接
if (1 == (footmin - headmax)){
//检查后部分是否密集
if (footlength > (footmax - footmin)){
//后半部分密集分布
minque = footmax +1;
} else {
minque = zhaoque(footArray);
}
} else {
minque = headmax +1;
}
} else {
minque = zhaoque(headArray);
}
}
}
return minque;
}

Answer 2

和找最大值一样。

对于有n个元素的数组a，就是先找出n-1个元素的距离集..找出最大值

int[] a = new int[]{1,2,3,6,10};//从小到大排序过，没有就要先排序
int max=0;
for(int i=1;i<a.length;i++){
   int d=a[i]-a[i-1];
   max=d>max? d:max;
}
System.out.println("Max:"+max);

追问

这种方法是一般方法,但是10W数量级性能很差,而且数组还是乱序..

追答

首先你转述的题目和所举的例子比你拿到原题都更简陋...就缺少了(让别人代你追求效率)所需的精确题意....

你给出的是“有序”的例子，乱序情况的“空缺数”具体所指就含糊了。比如[1,5,2]最大的是1,5之间的4？还是排序后[1,2,5]的3..。。

你说找出“最小”空缺数，但例子里面给出的是“最大”空缺值4...自相矛盾怎么去追求效率？

由于你的不精确，别人只能给出基本适用的方案....而且所给出的已经是空间时间上都是O(1)的算法(对每个输入只执行固定的几条指令)..再提高就是改成对应cpu核数的多线程.不属于算法了..

本回答被提问者和网友采纳