用列表遞歸地找到最大值

我試圖編寫的這個方法在列表中查找整數的最大值，並且對於賦值我必須使用遞歸。我想我理解遞歸的概念，但用列表或數組來做這件事是我不明白的。它總是需要將列表或數組分爲一半嗎？無論如何，這段代碼將被編譯，但我在下面評論的一行中得到了一個IndexOutOfBounds錯誤。它看起來遠離我應該做的事情嗎？用列表遞歸地找到最大值

public static final int findMaxRecursively(List<Integer> numbers) { 
int max = 0; 

    if(numbers.size() == 1) 
     return numbers.size(); 

    List<Integer> bottomHalf = new ArrayList<Integer>(numbers.size()/2); 
    for (int i= 0; i<numbers.size()/2;i++){ 
     if (bottomHalf.get(i) > max) // here's where the IndexOutOfBounds error occurs 
      max = bottomHalf.get(i); 
      } 
      findMaxRecursively(bottomHalf); 

    List<Integer> topHalf = new ArrayList<Integer>(numbers.size()/2); 
    for(int i = numbers.size()/2; i< numbers.size(); i++){ 
     if (topHalf.get(i) > max) 
     max = topHalf.get(i); 
    } 
     findMaxRecursively(topHalf); 

     return max; 
}

來源

2015-03-03 TonyKazanjian

從文檔，'ē得到（INT指數）拋出： IndexOutOfBoundsException - 如果索引超出範圍（index <0 ||指數> =大小（））'即使你'名單<整數myArray = new ArrayList <>（4）;'，你仍然會得到'myArray.size（）== 0'爲true。 – Shashank 2015-03-03 07:05:00

你的遞歸調用是沒有意義的，因爲你傳遞給他們空列表，即使他們回到正確的值，你是不是做與返回的任何有價值的東西。

爲了遞歸地查找最大元素，您應該拆分列表。最有效的分割是兩個相等的部分。

通過new ArrayList<Integer>(numbers.size()/2)創建列表不會將原始列表的一半元素複製到此列表中。它只是創建一個空的列表，其初始容量是原始列表大小的一半。您可以使用List<E> subList(int fromIndex, int toIndex);來查看列表的一部分。

而當numbers.size() == 1，你應該返回numbers.get(0)而不是numbers.size()。

最後，讓for循環失敗了遞歸解決方案的目的。在遞歸解決方案中，您只需進行2次遞歸調用即可獲得下半部分和上半部分的最大值，然後比較兩個返回值並返回較大值。

public static final int findMaxRecursively(List<Integer> numbers) 
{ 
    if(numbers.size() == 1) 
     return numbers.get(0); 

    List<Integer> bottomHalf = numbers.subList(0,numbers.size()/2); 
    int bottom = findMaxRecursively(bottomHalf); 

    List<Integer> topHalf = numbers.subList(numbers.size()/2,numbers.size()); 
    int top = findMaxRecursively(topHalf); 

    return top>bottom?top:bottom; 
}

來源

2015-03-03 06:43:25 Eran

非常好，謝謝！我不知道subList方法，但這很有道理。 – TonyKazanjian 2015-03-03 07:42:36

用列表遞歸地找到最大值

回答

相關問題