echo

任生命穿梭 时间的角落

0%

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

Posted on In Valine:

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

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)。

image-20210302095000679
上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。

示例:

1
2
3
4
5
6
7
8
9
10
11
给定 matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

说明:

  1. 你可以假设矩阵不可变。
  2. 会多次调用 sumRegion 方法。
  3. 你可以假设 row1 ≤ row2 且 col1 ≤ col2。

方法一：二维前缀和

注意到矩阵不可变，我们可以使用二维数组保存数组的前缀和，然后就可以在O(1)时间复杂度内查到区域和。对于示例中的数组我们建立如下前缀和数组：

1
2
3
4
5
6
0	0	0	0	0	0	
0	3	3	4	8	10	
0	8	14	18	24	27	
0	9	17	21	28	36	
0	13	22	26	34	49	
0	14	23	30	38	58

题中数组下标范围是0 <= row < matrix.length和0 <= col < matrix[0].length。子矩阵左上角(row1,col1)，右下角(row2,col2)。子矩阵和 = sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - sum[row1][col2 + 1] + sum[row1][col1]。sum 数组多加一行一列是为了避免计算时下标是否越界判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class NumMatrix {
    private int[][] sum;

    public NumMatrix(int[][] matrix) {
        if(matrix.length == 0 || matrix[0].length == 0){
            return;
        }

        sum = new int[matrix.length + 1][matrix[0].length + 1];
		//计算 sum 数组
        for(int i = 1; i < sum.length; i++){
            for(int j = 1; j < sum[0].length; j++){
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }

    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2 + 1][col2 + 1] - sum[row1][col2 + 1] - sum[row2 + 1][col1] + sum[row1][col1];
    }
}

/**
 * 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(1)，其中 m 和 n 分别为数组的行数和列数。
  • 空间复杂度O(mn)