Получение наибольшего элемента в массиве с помощью рекурсии


Любые предложения о том, как сделать этот код более эффективным?

import java.util.Scanner;
public class RecursionLargestInArray 
{ 
public static void main (String[] args) 
{ 
    int max = -999; 
    Scanner scan = new Scanner (System.in); 
    System.out.print("Enter the size of the array: "); 
    int arraySize = scan.nextInt(); 
    int[] myArray = new int[arraySize]; 
    System.out.print("Enter the " + arraySize + " values of the array: "); 
    for (int i = 0; i < myArray.length; i++) 
        myArray[i] = scan.nextInt(); 
    for (int i = 0; i < myArray.length; i++) 
        System.out.println(myArray[i]); 
    System.out.println("In the array entered, the larget value is " 
                        + getLargest(myArray, max) + "."); 
} 

public static int getLargest(int[] myArray, int max) 
{     
    int i = 0, j = 0, tempmax = 0; 
    if (myArray.length == 1) 
    { 
        return myArray[0] > max ? myArray[0] : max; 
    } 
    else if (max < myArray[i]) 
    { 
        max = myArray[i]; 
        int[] tempArray = new int[myArray.length-1]; 
        for (i = 1; i < myArray.length; i++) 
        { 
            tempArray[j] = myArray[i]; 
            j++; 
        } 
        tempmax = getLargest(tempArray, max); 
        return tempmax; 
    } 
    else
    { 
        int[] tempArray = new int[myArray.length-1]; 
        for (i = 1; i < myArray.length; i++) 
        { 
            tempArray[j] = myArray[i]; 
            j++; 
        } 
        tempmax = getLargest(tempArray, max); 
        return tempmax; 
    } 
} 
}


14819
7
задан 15 ноября 2011 в 03:11 Источник Поделиться
Комментарии
4 ответа

Я хотел бы использовать вспомогательную функцию, и я хотел бы избежать копирования массива (вместо использования индексов):

public static int getLargest(int ... myArray) {
return getLargest(myArray, 0, myArray.length);
}

private static int getLargest(int[] myArray, int from, int to) {
if(from == to) {
throw new IllegalArgumentException("empty array");
} else if (from + 1 == to) {
return myArray[from];
} else {
int middle = (from + to) / 2;
return Math.max(getLargest(myArray, from, middle),
getLargest(myArray, middle, to));
}
}

Используя с varargs инт ... вместо массива типа int[] в качестве аргумента, делает ее более гибкой, например, лучше проверить.

В случае, если вы действительно хотите скопировать массив, используйте систему.arraycopy, что гораздо быстрее проезжать.

6
ответ дан 15 ноября 2011 в 03:11 Источник Поделиться

Это ситуация, когда указатели в C будет полезно (или хвостовой рекурсии в функциональных языках), но мы будем работать с тем что есть. Поскольку это выглядит как домашнее задание, я постараюсь, чтобы направлять вас к решению, а не просто давать его.

Создаем новый массив для каждого Рекурсия-это ужасно неэффективно. Вы можете сделать это инлайн, просто передать указатель на позицию вы в настоящее время в массиве.

Я думаю, что этого должно быть достаточно, добавьте комментарий, если вам нужно больше.

Редактировать: вы даже не нужен максимум в качестве аргумента.

4
ответ дан 15 ноября 2011 в 03:11 Источник Поделиться


  1. Если вы используете вернуться в состояние, нужно собраться следующий код внутри другого? (пример: если в getLargest() метод)

  2. Второй и третий блоки кода в getLargest() способ повторять много кода, я уверен, что вы можете выяснить, хороший способ, чтобы избежать этого повторения;

  3. @Кевин делает очень хороший момент, вам действительно нужно создать новый массив на каждой итерации?

  4. Что если пользователь отвечает на -1 на первый вопрос?

  5. Что бы ваш программу ответ на ввода 3 и затем -1020, -1050, -1013?

3
ответ дан 15 ноября 2011 в 04:11 Источник Поделиться

Вот небольшая Java-программа, чтобы найти максимальный элемент в массиве рекурсивно

public class TestProgram {
private int[] a = { 3, 5, 2, 8, 4, 9 };

public static void main(String[] args) {
TestProgram p = new TestProgram();
int result = p.findMax(0);
System.out.printf("Max element = %d", result);
}

public int findMax(int i) {
// the anchor of the recursive method
if (i == a.length)
return Integer.MIN_VALUE;

return Math.max(a[i], findMax(i + 1));
}
}

1
ответ дан 16 мая 2012 в 03:05 Источник Поделиться