美文网首页程序员
力扣 304 二维区域和检索 - 矩阵不可变

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

作者: zhaojinhui | 来源:发表于2020-10-30 09:08 被阅读0次

题意:给定一个二维数组,给定一个区间,返回该区间的二维数组中元素的和

思路:

  1. 遍历数组,计算每一个节点,到左上节点对应的矩阵中的点的和
  2. 对于每一个给定的区间矩阵,把该矩阵的四个点到左上点的区间,分割成四部分,结果=整体-左部-上部+左上部

思想:数组的遍历

复杂度:时间O(n2),空间O(n2)

class NumMatrix {
    int[][] temp;
    int m;
    int n;
    public NumMatrix(int[][] matrix) {
        m = matrix.length;
        if(m == 0)
            return;
        n = matrix[0].length;
        temp = new int[m][n];
        if(n == 0)
            return;
        
        temp[0][0] = matrix[0][0];
        for(int i=1;i<m;i++) {
            temp[i][0] = temp[i-1][0] + matrix[i][0];
        }
        for(int j=1;j<n;j++) {
            temp[0][j] = temp[0][j-1] + matrix[0][j];
        }
        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                temp[i][j] = matrix[i][j] - temp[i-1][j-1] + temp[i-1][j] + temp[i][j-1];   
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(row1 < 0 || col1 < 0 || row2 >= m || col2 >= n)
            return 0;
        int top = 0;
        int left = 0;
        int overlap = 0;
        if(row1>0) 
            top = temp[row1-1][col2];
        if(col1>0)
            left = temp[row2][col1-1];
        if(row1 > 0 && col1 > 0)
            overlap = temp[row1-1][col1-1];
        return temp[row2][col2] - top - left + overlap;
    }
}

相关文章

网友评论

    本文标题:力扣 304 二维区域和检索 - 矩阵不可变

    本文链接:https://www.haomeiwen.com/subject/wpzzmktx.html