<span>【题解】力扣304. 二维区域和检索 - 矩阵不可变</span>

题目来源

二维区域和检索 - 矩阵不可变

思路

方法一

一维前缀和

创建m行,n+1列的二位前缀和数组

class NumMatrix {

    int sum[][];

    public NumMatrix(int[][] matrix) {
        int r = matrix.length;
        int c = matrix[0].length;
        sum = new int[r][c+1];
        for(int i = 0;i<r;i++){
            for(int j = 0;j<c;j++){
                sum[i][j+1] = sum[i][j]+matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int ans = 0;
        for(int i = row1;i<=row2;i++){
            ans += sum[i][col2+1] - sum[i][col1];
        }
        return ans;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

复杂度分析:

  • 时间复杂度:O(mn)
  • 空间复杂度:O(mn)

方法二

二维前缀和

如图:

二维前缀和数组中的每一个格子,比如f[i][j],就是从(i,j)为右下角,(0,0)为左上角,这一个区域内的数字总和。

预设二维前缀和的第0行和第0列都为0,如上图所示,可以求出二维前缀和数组的每一个位置。

int n = matrix.length;
int m = matrix[0].length;
sum = new int[n + 1][m + 1];
// 预处理除前缀和数组(模板部分)
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
    }
}

求出二维前缀和数组后,当我们要求\((x_1,y_1)\)作为左上角,\((x_2,y_2)\)作为右下角的区域和的时候,可以直接利用前缀和数组快速求解。如下图所示。

由于原数组的下标是从0开始的,因此,在用二维前缀和数组计算的时候,要在给定的原数组的坐标基础上加1

public int sumRegion(int x1, int y1, int x2, int y2) {
    // 但由于我们源数组下标从 0 开始,因此要在模板的基础上进行 + 1
    x1++; y1++; x2++; y2++;
    return f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1];
}

参考来源

  1. 官方题解
  2. 宫水三叶
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-01 12:22
点赞 评论 收藏
分享
06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务