我必须编写一个方法来返回矩阵中"a"个字符的计数，但我必须使用递归，并且它必须是O(n.log(n((。
这是我的非递归代码：
public static int acount(char[][] mat) {
int result = 0;
int i = 0;
int j = 0;
while (i <= 4) {
if (mat[i][j] == 'a') {
result++;
j++;
}
if (mat[i][j] == 'b') {
i++;
j = 0;
}
}
return result;
}
这是我尝试过的，但有一个错误："；线程中的异常"；主"；java.lang.StackOverflowError"：
public static int acount(char[][] mat) {
int result = 0;
int i = 0;
int j = 0;
while (mat[i][j] == 'a') {
result++;
j++;
}
if (i < 5) {
i++;
j = 0;
} else {
return result;
}
return acount(mat);
}
这是主要代码：
public static void main(String[] args) {
int n = 5;
Random rand = new Random();
char[][] input = new char[n][n];
for (int i = 0; i < n; i++) {
int a_num = rand.nextInt(n);
for (int j = 0; j < a_num; j++) {
input[i][j] = 'a';
}
for (int j = a_num; j < n; j++) {
input[i][j] = 'b';
}
}
System.out.println(Arrays.deepToString(input));
System.out.println(acount(input));
}
}
如何解决？
好的，让我们从您的原始版本开始。
public static int acount(char[][] mat) {
int result = 0;
int i = 0;
int j = 0;
while (i <= 4) {
if (mat[i][j] == 'a') {
result++;
j++;
}
if (mat[i][j] == 'b') {
i++;
j = 0;
}
}
return result;
}
此代码看起来有问题。首先，它假设您的输入只包含a或b。如果您包含其他数据，则永远不会递增i或j，并且永远循环。看起来你还假设矩阵中的每一行都是a-a-b-who-car。也就是说，都是a，但你不再看第一个b了。这是你真正想要的吗？也许是。
我会把它写成：
for (int index1 = 0; index1 < 5; ++index1) {
for (int index2 = 0; index2 < 5; ++index2) {
if (mat[index1][index2] == 'a') {
++result;
}
}
}
实际上，我不会硬编码5，而是分别使用mat.length和mat[index1].length。
至于堆栈溢出，这是因为递归永远不会结束。你这样做：
return acount(mat);
也就是说，您再次用相同的数组调用acount，它再次调用acount，它再次呼叫acount。。。
唯一不会失败的方法是，如果上面的代码提前返回，那么它可能不会。我认为您缺少的是，每次输入acount时，都会得到新的变量，所以I和j再次以零开始。
您可以通过将i传递到acount中来部分解决此问题，当您递归时：
return acount(mat, i+1);
这将解决一些问题，尽管我认为你的复杂性仍然是O(n^2(。
然后让我们看看这个：
while (mat[i][j] == 'a') {
result++;
j++;
}
如果这一行中从来没有a，会发生什么？它看起来越过了数组的末尾。你对输入数据做出了假设，这会让你很痛苦。