递归地对数组中的整数求和
我有一个程序,我正在尝试为类返回使用递归返回数组中所有整数的总和。 这是我迄今为止的计划:
public class SumOfArray { private int[] a; private int n; private int result; public int sumOfArray(int[] a) { this.a = a; n = a.length; if (n == 0) // base case result = 0; else result = a[n] + sumOfArray(a[n-1]); return result; } // End SumOfArray method } // End SumOfArray Class
但我相信,我得到的三个错误都是相关的,但我无法弄清楚为什么它会找到一种null:
SumOfArray.java:25: sumOfArray(int[]) in SumOfArray cannot be applied to (int) result = a[n] + sumOfArray(a[n-1]); ^ SumOfArray.java:25: operator + cannot be applied to int,sumOfArray result = a[n] + sumOfArray(a[n-1]); ^ SumOfArray.java:25: incompatible types found : required: int result = a[n] + sumOfArray(a[n-1]); ^ 3 errors
解决方案比它看起来更简单,试试这个(假设一个长度非零的数组):
public int sumOfArray(int[] a, int n) { if (n == 0) return a[n]; else return a[n] + sumOfArray(a, n-1); }
这样叫:
int[] a = { 1, 2, 3, 4, 5 }; int sum = sumOfArray(a, a.length-1);
问题是a[n-1]
是一个int
,而sumOfArray
需要一个 int
数组 。
提示:您可以通过使sumOfArray
获取数组和起始(或结束)索引来简化操作。
a[n-1]
是在n-1处得到int,而不是从0到n-1的数组。
尝试使用
Arrays.copyOf(a, a.length-1);
代替
a
是一个int
数组。 因此a[n-1]
是int
。 您正在将一个int
传递给sumOfArray
,它需要一个数组而不是一个int
。
如果您不想传递数组的长度,请尝试此操作:
private static int sumOfArray(int[] array) { if (1 == array.length) { return array[array.length - 1]; } return array[0] + sumOfArray(Arrays.copyOfRange(array, 1, array.length)); }
当然你需要检查数组是否为空。
这是具有复杂度O(N)和输入参数A []的一种递归解决方案。
您可以处理null和empty(0 length)情况,特别是它在此解决方案中返回0。 在这种情况下,您也会抛出exception。
/* * Complexity is O(N) */ public int recursiveSum2(int A[]) { if(A == null || A.length==0) { return 0; } else { return recursiveSum2Internal(A,A.length-1); } } private int recursiveSum2Internal(int A[],int length) { if(length ==0 ) { return A[length]; } else { return A[length]+recursiveSum2Internal(A, length-1); } }
这个递归解决方案怎么样? 您创建一个较小的子数组,其中包含从第二个到最后的元素。 此递归将继续,直到数组大小变为1。
import java.util.Arrays; public class Sum { public static void main(String[] args){ int[] arr = {1,2,3,4,5}; System.out.println(sum(arr)); // 15 } public static int sum(int[] array){ if(array.length == 1){ return array[0]; } int[] subArr = Arrays.copyOfRange(array, 1, array.length); return array[0] + sum(subArr); } }
private static int sum(int[] arr) { // TODO Auto-generated method stub int n = arr.length; if(n==1) { return arr[n-1]; } int ans = arr[0]+sum(Arrays.copyOf(arr, n-1)); return ans; }