我尝试使用我对分而治之算法的理解来找到整数数组中的最小元素。 我得到了正确的结果。 但我不确定这是否是使用分而治之算法的传统方法。 如果有任何其他比我尝试过的更聪明的方法来实现分而治之算法,请告诉我。
public static int smallest(int[] array){
int i = 0;
int array1[] = new int[array.length/2];
int array2[] = new int[array.length - (array.length/2)];
for(int index = 0; index < array.length/2 ; index++){
array1[index] = array[index];
}
for(int index = array.length/2; index < array.length; index++){
array2[i] = array[index];
i++;
}
if(array.length > 1){
if(smallest(array1) < smallest(array2)){
return smallest(array1);
}else{
return smallest(array2);
}
}
return array[0];
}
最佳答案
您的代码是正确的,但您可以使用 Arrays.copyOfRange
和 Math.min
等现有函数编写更少的代码
public static int smallest(int[] array) {
if (array.length == 1) {
return array[0];
}
int array1[] = Arrays.copyOfRange(array, 0, array.length / 2);
int array2[] = Arrays.copyOfRange(array, array.length / 2, array.length);
return Math.min(smallest(array1), smallest(array2));
}
还有一点。在开头测试 length == 1
是更具可读性的版本。从功能上来说,它是相同的。从性能角度来看,它创建了更少的数组,并尽快从 smallest
函数中退出。
也可以使用不同形式的递归,而无需创建新数组。
private static int smallest(int[] array, int from, int to) {
if (from == to) {
return array[from];
}
int middle = from + (to - from) / 2;
return Math.min(smallest(array, from, middle), smallest(array, middle + 1, to));
}
public static int smallest(int[] array){
return smallest(array, 0, array.length - 1);
}
第二个版本更高效,因为它不会创建新数组。
关于java - 使用分而治之算法在java中查找整数数组中的最小元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31681671/