java - 使用分而治之算法在java中查找整数数组中的最小元素

Question

我尝试使用我对分而治之算法的理解找到整数数组中的最小元素。我得到正确的结果。但我不确定这是否是使用分而治之算法的传统方式。如果有比我尝试过的更智能的分而治之算法的其他实现方式，请告诉我。

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];
   }

Answer 1

您的代码是正确的，但是您可以使用 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);
}

第二个版本效率更高，因为它不会创建新数组。