我尝试编写的此方法在列表中查找整数的最大值,对于赋值,我必须使用递归。我想我了解递归的概念,但是用列表或数组来做是我不了解的事情。是否总是需要将列表或数组分成两半?无论如何,此代码都可以编译,但是我在下面的注释行中出现了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;
}
递归调用没有意义,因为您将空列表传递给了它们,即使它们返回了正确的值,也不会对返回的值做任何事情。
为了递归地找到max元素,您应该拆分列表。最有效的分割是分成两个相等的部分。
创建列表依据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;
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句