X

LEETCODE 1314. Matrix Block Sum 解题思路分析

题目大意:

矩阵区域和

给你一个 m * n 的矩阵 mat 和一个整数 K ,请你返回一个矩阵 answer ,其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和:

  • i - K <= r <= i + K, j - K <= c <= j + K
  • (r, c) 在矩阵内。

示例 1:

输入:mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
输出:[[12,21,16],[27,45,33],[24,39,28]]

示例 2:

输入:mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
输出:[[45,45,45],[45,45,45],[45,45,45]]

提示:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n, K <= 100
  • 1 <= mat[i][j] <= 100

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1314

解题思路分析:

因为题目给出的矩阵规模不大,所以本题使用暴力解是可行的。暴力解需要4层循环,前两层循环是循环矩阵的每一个点,另外两层循环是来判断矩阵内符合当前点累加对象的点。暴力解法的代码会在文章的最后给出。

我们先来看一种高效的解法。本题的实质是求矩阵内某个子矩阵内所有数值的和。对于子矩阵的取值范围,取决于返回结果当前坐标以及K值,比如当前坐标为(i, j),那么子矩阵的范围应该是P1: (i-k, j-k),P2: (i+k, j+k)代表的子矩阵。其中P1代表子矩阵的左上点,P2为右下点。这里需要注意两个顶点P1和P2是否在矩阵内部,也就是说,i-k和j-k应该大于等于0,同理i+k和j+k也要分别小于行数与列数。总结一下:

int p1_X = max(0, i-k);
int p1_Y = max(0, j-k);
int p2_X = min(rowCount-1, i+k);
int p2_Y = min(colCount-1, j+k);

对于求子矩阵内所有数值和的问题,我们可以采用前缀和方式求解,我们定义一个二维前缀和数组presum,presum[i][j]代表点(i, j)到(0, 0)范围内所有数字和。这类题型我在之前的文章介绍过,可以参考 LEETCODE 308. Range Sum Query 2D – Mutable 解题思路分析 这篇文章。对于任意区间内[x1, y1], [x2, y2]的数值和应该等于:

sum([x1,y1],[x2,y2]) = presum[x2][y2]
                     - presum[x1-1][y2]
                     - presum[x2][y1-1]
                     + presum[x1-1][y1-1];

如果感觉公式过于抽象,我们可以参考下图:

上图最左侧红色区域是我们想求和的区域,它的和应该等于蓝色区域减去2个黄色区域的值,而被减去的2个黄色区域存在一个橘红色重复区域(参照上图最右侧),因此还要再加上这个橘色区域即是我们想求的红色区域和。对于蓝色,黄色以及橘色区域都是前缀和数组中存在的值。

因此解题时我们需要2个步骤:

  1. 首先求出前缀和数组
  2. 循环矩阵每一个点,查看该点的合理子矩阵范围,利用前缀和数组求该范围内数值和。

实现代码:

public int[][] matrixBlockSum(int[][] mat, int K) {
    // 前缀和数组
    int[][] presum = new int[mat.length][mat[0].length];
    // 计算前缀和
    for(int i=0;i<mat.length;i++){
        int sum=0;
        for(int j=0;j<mat[0].length;j++){
            sum+=mat[i][j];
            presum[i][j]=sum;
            if(i>0) presum[i][j]+=presum[i-1][j];
        }
    }
    // 返回结果
    int[][] res = new int[mat.length][mat[0].length];
    // 循环每个点
    for(int i=0;i<mat.length;i++){
        for(int j=0;j<mat[0].length;j++){
            // 计算出对于该点存在的合理子矩阵范围
            int minR=Math.max(0,i-K);
            int maxR=Math.min(mat.length-1,i+K);
            int minC=Math.max(0,j-K);
            int maxC=Math.min(mat[0].length-1,j+K);
            // 利用前缀和数组计算该子矩阵内所有数字和
            res[i][j]=presum[maxR][maxC];
            if(minR>0) res[i][j]-=presum[minR-1][maxC];
            if(minC>0) res[i][j]-=presum[maxR][minC-1];
            if(minR>0&&minC>0) res[i][j]+=presum[minR-1][minC-1];
        }
    }
    return res;
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 96.32% of Java online submissions for Matrix Block Sum.Memory Usage: 42.2 MB, less than 100.00% of Java online submissions for Matrix Block Sum.


解法二:暴力解

public int[][] matrixBlockSum(int[][] mat, int K) {
    // 返回结果
    int[][] res = new int[mat.length][mat[0].length];
    // 循环每个点
    for(int i=0;i<mat.length;i++){
        for(int j=0;j<mat[0].length;j++){
            // 子矩阵数字和
            int sum=0;
            // 子矩阵合理范围
            int minR=Math.max(0,i-K);
            int maxR=Math.min(mat.length-1,i+K);
            int minC=Math.max(0,j-K);
            int maxC=Math.min(mat[0].length-1,j+K);
            // 循环子矩阵每个点,计算数字和
            for(int r=minR;r<=maxR;r++){
                for(int c=minC;c<=maxC;c++){
                    sum+=mat[r][c];
                }
            }
            // 将子矩阵的和更新至返回结果
            res[i][j]=sum;
        }
    }
    return res;
}

解法二暴力解的执行时间为75ms。

Runtime: 75 ms, faster than 45.25% of Java online submissions for Matrix Block Sum.

Memory Usage: 43.3 MB, less than 100.00% of Java online submissions for Matrix Block Sum.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1314-matrix-block-sum-解题思路分析/
Categories: leetcode
kwantong:

View Comments (1)

  • After checking out a handful of the blog articles on your web site, I honestly like your way of writing
    a blog. I bookmarked it to my bookmark site
    list and will be checking back in the near future. Please
    check out my website as well and let me know what you think.