递归地计算数组中的元素数量 - 处理大型数组

Question

递归地计算数组中的元素数量 - 处理大型数组

3

我正在学习递归，并且我需要创建一个递归方法来计算数组中特定数字的出现次数，例如：{1,2,3,4,4,5}中数字4的出现次数应该为2。我知道递归不是解决此问题的理想方法，使用endIndex也不是理想选择，但这只是教科书上的问题，我似乎无法解决。

我的方法不太好用，因为在处理大型数组时我总是会耗尽堆。如何优化这样的代码？谢谢！

 public static int countNumber(int[] array, int startIndex, int endIndex, int 
   number) {
    int result = 0;
    if (startIndex==endIndex) {
        return result;
    }
    if (array[startIndex] == number ) {
        result++;
    }
    result = result + countNumber(array,startIndex+1,endIndex,number);
    return result;
   }

- user11104002

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Forketyfork · Accepted Answer

你确定是堆(heap)耗尽了，而不是栈(stack)？因为在大型数组中，栈耗尽是一件比较常见的事情。递归的深度总是受到栈大小的限制。

你可以在每次迭代中将数组分成两部分，并在这两个部分上递归地运行该方法。这样，对于输入数组的n个元素，递归的深度将是log2(n)而不是n。代码如下：

if (startIndex == endIndex) {
    if (array[startIndex] == number) {
        return 1;
    }
    return 0;
}
return countNumber(array, startIndex, (startIndex + endIndex) / 2, number)
        + countNumber(array, (startIndex + endIndex) / 2 + 1, endIndex, number);

当然，你也可以增加堆栈大小（例如使用 -Xss10m 参数），或者简单地限制输入数组的大小。