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

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

在处理一个整数数组时，如果数组中的数字不连续，找出最小的空缺数字是一个常见的需求。例如，给定数组为 {1, 2, 3, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}，我们需要找到数组中最小的缺失整数。这个问题可以通过递归的方法来解决。

首先，我们定义一个主方法，该方法接收一个整数数组作为输入，并调用辅助方法来找到最小的空缺数字。主方法中的代码如下：

java

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);

}

辅助方法 `zhaoque` 用于递归地查找最小的空缺数字。以下是该方法的实现：

java

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;

}

通过这种方法，我们可以有效地找出给定数组中最小的空缺数字。2024-12-16