Java递归统计5x5二维矩阵'a'字符 要求O(n log n)解决栈溢出问题
问题根因排查
- 无限递归触发栈溢出:原递归实现没有把遍历位置、累计计数作为参数传递。每次调用
acount(mat)时,方法内部都会重新将i、j、result初始化为0:哪怕在当前栈帧中临时把i改成下一行的起始位置,下一层递归启动后又会从矩阵左上角(0,0)重新开始扫描,永远走不到i <5判断后的返回分支,持续在栈上创建新的方法栈帧,最终触发StackOverflowError。 - 计数逻辑完全失效:就算递归能正常终止,每次进入方法都会把
result重置为0,之前扫描累计的字符数量不会传递到下一层递归,最终返回的结果和实际矩阵中'a'的数量完全不符。 - 边界校验缺失:代码中直接访问
mat[i][j]时没有校验下标范围,遇到某行全是'a'的场景时,j会持续自增超出行数组的长度,触发数组下标越界异常。 - 时间复杂度不达标:逐元素扫描全矩阵的时间复杂度为O(n²),不符合题目要求的O(n log n)约束。
解决思路
结合测试代码生成矩阵的特性(每一行的字符是前半段连续'a'、后半段连续'b',行内元素有序),设计符合O(n log n)要求的递归实现:
- 保留对外的方法签名兼容原有调用逻辑,内部通过带参数的递归核心方法传递动态状态,不再在方法内部硬编码初始化遍历位置。
- 对每一行使用二分查找定位第一个'b'的位置,这个位置的下标就是当前行包含的'a'的数量。二分查找本身的时间复杂度是O(log n),n行的总时间复杂度为O(n log n),满足题目要求。
- 设置明确的递归终止条件:当行索引超出矩阵的总行数时,直接返回累计的计数值,结束递归,避免无限栈堆积。
修正后的递归实现代码
// 对外暴露的入口方法,和原有调用逻辑完全兼容 public static int acount(char[][] mat) { // 递归初始状态:从第0行开始遍历,累计计数为0 return countRecursive(mat, 0, 0); } // 递归核心方法,携带动态遍历参数 private static int countRecursive(char[][] mat, int currentRow, int accumCount) { // 递归终止条件:所有行处理完毕,返回累计结果 if (currentRow >= mat.length) { return accumCount; } char[] row = mat[currentRow]; // 二分查找当前行中第一个'b'的位置,即当前行'a'的总个数 int left = 0, right = row.length - 1; int firstBPos = row.length; // 整行都是'a'的场景下,b的位置为行长度 while (left <= right) { int mid = left + (right - left) / 2; if (row[mid] == 'b') { firstBPos = mid; right = mid - 1; } else { left = mid + 1; } } // 累加当前行的a计数,递归处理下一行 return countRecursive(mat, currentRow + 1, accumCount + firstBPos); }
修正后效果验证
- 递归路径明确,每次递归处理一行,总递归深度等于矩阵行数n,不会出现无限递归,从根源上避免栈溢出问题。
- 每一行通过二分查找完成统计,总时间复杂度为O(n log n),完全符合题目要求。
- 逐行累计计数,结果和矩阵中实际的'a'数量完全一致,没有逻辑偏差。
内容的提问来源于stack exchange,提问作者Meysab
相关产品推荐
相关产品推荐

