You need to enable JavaScript to run this app. Java递归统计5x5二维矩阵'a'字符 要求O(n log n)解决栈溢出问题
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.30 09:54:10