LeetCode题练习与总结：二维区域和检索 - 矩阵不可变--304

一、题目描述

给定一个二维矩阵 matrix，以下类型的多个请求：

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

实现 NumMatrix 类：

• NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
• int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。

示例 1：

输入: 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出: 
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[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]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• -10^5 <= matrix[i][j] <= 10^5
• 0 <= row1 <= row2 < m
• 0 <= col1 <= col2 < n
• 最多调用 10^4 次 sumRegion 方法

二、解题思路

这个问题可以通过使用一个辅助的前缀和矩阵来解决。前缀和矩阵是一个二维数组，其中每个元素 dp[i][j] 表示从原点 (0, 0) 到 (i-1, j-1) 形成的矩形区域的所有元素之和。

初始化时，我们遍历整个输入矩阵，并计算每个位置的前缀和。计算前缀和时，可以使用以下关系：

dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1]

这里的 dp[i-1][j] 是当前位置上方元素的前缀和，dp[i][j-1] 是当前位置左侧元素的前缀和，而 dp[i-1][j-1] 是左上角元素的前缀和，我们加了一次，所以要减去。最后加上当前位置的元素值 matrix[i-1][j-1]。

当我们需要计算 (row1, col1) 到 (row2, col2) 的子矩阵和时，我们可以利用前缀和矩阵快速计算：

sumRegion(row1, col1, row2, col2) = dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1] + dp[row1][col1]

这里的 dp[row2+1][col2+1] 是 (row2, col2) 的前缀和，而其他三项分别减去的是超出 (row1, col1) 到 (row2, col2) 范围的部分。

三、具体代码

class NumMatrix {
    private int[][] dp;

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

在这个实现中，我们初始化了一个大小为 (m+1) x (n+1) 的前缀和矩阵 dp，以处理边界情况，这样我们就不需要在计算时对边界进行特殊处理。每次调用 sumRegion 方法时，我们只需要常数时间复杂度即可得到子矩阵的和。

四、时间复杂度和空间复杂度

1. 时间复杂度

• 构造函数 NumMatrix(int[][] matrix)：

  • 该函数包含两个嵌套循环，分别遍历矩阵的行和列。
  • 每次循环中，计算前缀和的操作是常数时间的。
  • 因此，构造函数的时间复杂度为 O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。

• 方法 sumRegion(int row1, int col1, int row2, int col2)：

  • 该方法直接从前缀和数组中提取四个值进行计算，不涉及任何循环。
  • 因此，该方法的时间复杂度为 O(1)，即常数时间。

2. 空间复杂度

• 构造函数 NumMatrix(int[][] matrix)：
  • 该函数创建了一个大小为 (m + 1) x (n + 1) 的二维数组 dp，用于存储前缀和。
  • 因此，空间复杂度为 O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。

五、总结知识点

1. 类定义：定义了一个名为 NumMatrix 的类，包含私有成员变量 dp 和两个公共方法。

2. 二维数组：使用二维数组 dp 来存储前缀和，这是解决子矩阵求和问题的关键。

3. 构造函数：NumMatrix 类的构造函数接受一个二维数组 matrix 作为参数，并初始化前缀和数组 dp。

4. 边界检查：在构造函数中，首先检查输入矩阵是否为空，这是防御性编程的一种实践。

5. 嵌套循环：在构造函数中使用嵌套循环来计算前缀和数组 dp 的每个元素。

6. 前缀和算法：通过累加前缀和数组中的值来计算任意子矩阵的和，这是算法的核心。

7. 空间优化：通过使用 (m + 1) x (n + 1) 大小的前缀和数组，避免了在计算子矩阵和时的边界问题。

8. 数组索引操作：在 sumRegion 方法中，通过正确的索引操作来获取前缀和数组中的值。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。

原文地址：https://blog.csdn.net/weixin_62860386/article/details/142892014

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！