[leetcode]304. 二维区域和检索 - 矩阵不可变(二维前缀和）

逃离我推掉我的手 2022-11-04 11:12 174阅读 0赞

### 目录 ###

*   *  题目描述
     *  解题思路
     *   *  二维前缀和
     *  复杂度分析
     *  代码实现（Python）
     *  Tips

## 题目描述 ##

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

![在这里插入图片描述][20210302093029281.png_type_ZmFuZ3poZW5naGVpdGk_shadow_2_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDY4MjI5_size_10_color_FFFFFF_t_70]

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

*  **示例:**  
    给定 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。

> 题目链接：[https://leetcode-cn.com/problems/range-sum-query-2d-immutable][https_leetcode-cn.com_problems_range-sum-query-2d-immutable]

## 解题思路 ##

参考官方题解：

### 二维前缀和 ###

为了将每次检索的时间复杂度降到 O(1)，需要使用`二维前缀和`，在初始化的时候计算二维前缀和数组。

假设 `m` 和 `n` 分别是矩阵  m a t r i x matrix matrix 的行数和列数，定义当  0 ≤ i < m 0≤i<m 0≤i<m 且  0 ≤ j < n 0≤j<n 0≤j<n 时， f ( i , j ) f(i,j) f(i,j) 为矩阵  m a t r i x matrix matrix 的以  ( i , j ) (i,j) (i,j) 为右下角的子矩阵的元素之和。

*  当  i = 0 i = 0 i=0 或  j = 0 j = 0 j=0 时，计算  f ( i , j ) f(i, j) f(i,j) 只需要对矩阵  m a t r i x matrix matrix 的最上边的行和最左边的列分别计算前缀和即可。
 *  当  i > 0 i > 0 i>0 和  j > 0 j > 0 j>0时，假设计算  f ( i , j ) f(i,j) f(i,j) 时已经知道了  f ( i − 1 , j ) f(i−1,j) f(i−1,j)、 f ( i , j − 1 ) f(i,j−1) f(i,j−1) 和  f ( i − 1 , j − 1 ) f(i−1,j−1) f(i−1,j−1) 的值。为了计算  f ( i , j ) f(i,j) f(i,j)，想到使用  f ( i − 1 , j ) f(i−1,j) f(i−1,j)、 f ( i , j − 1 ) f(i,j−1) f(i,j−1) 和  m a t r i x \[ i \] \[ j \] matrix\[i\]\[j\] matrix\[i\]\[j\] 的值。如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDY4MjI5_size_16_color_FFFFFF_t_70]  
    检索时应利用预处理得到的  f f f 的值。当  r o w 1 = 0 row 1=0 row1=0 且  c o l 1 = 0 col 1 =0 col1=0 时， s u m R e g i o n ( r o w 1 , c o l 1 , r o w 2 , c o l 2 ) = f ( r o w 2 , c o l 2 ) sumRegion(row1,col1,row2,col2)=f(row2,col2) sumRegion(row1,col1,row2,col2)=f(row2,col2)。

当 r o w 1 < = r o w 2 row1<=row2 row1<=row2， c o l 1 < = c o l 2 col1<=col2 col1<=col2时：

s u m R e g i o n ( r o w 1 , c o l 1 , r o w 2 , c o l 2 ) = f ( r o w 2 , c o l 2 ) − f ( r o w 1 − 1 , c o l 2 ) − f ( r o w 2 , c o l 1 − 1 ) + f ( r o w 1 − 1 , c o l 1 − 1 ) sumRegion(row1,col1,row2,col2)=f(row2,col2)-f(row1-1,col2)-f(row2,col1-1)+f(row1-1,col1-1) sumRegion(row1,col1,row2,col2)=f(row2,col2)−f(row1−1,col2)−f(row2,col1−1)\+f(row1−1,col1−1)

具体实现时创建 m + 1 m+1 m\+1行 n + 1 n+1 n\+1列的二维数组 s u m s sums sums， s u m s \[ i + 1 \] \[ j + 1 \] sums\[i+1\]\[j+1\] sums\[i\+1\]\[j\+1\]即计算提到的 f ( i , j ) f(i,j) f(i,j)。

## 复杂度分析 ##

1.  时间复杂度：  
    初始化 O(mn)，每次检索 O(1)，其中 m 和 n 分别是矩阵 matrix 的行数和列数。  
    初始化需要遍历矩阵 matrix 计算二维前缀和，时间复杂度是 O(mn)。每次检索的时间复杂度是 O(1)。
2.  空间复杂度：  
    O(mn)，其中 m 和 n 分别是矩阵 matrix 的行数和列数。需要创建一个 m+1 行 n+1 列的二维前缀和数组 sums。

## 代码实现（Python） ##

class NumMatrix:
    
        def __init__(self, matrix: List[List[int]]):
            row, col = len(matrix), (len(matrix[0]) if matrix else 0)
            self.sums = [[0] * (col+1) for _ in range(row+1)]
            _sums = self.sums
            for r in range(row):
                for c in range(col):
                    _sums[r+1][c+1] = _sums[r][c+1] + _sums[r+1][c] - _sums[r][c] + matrix[r][c]
    
        def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
            _sums = self.sums
            return _sums[row2+1][col2+1] + _sums[row1][col1] - _sums[row1][col2+1] - _sums[row2+1][col1]
    
    
    # Your NumMatrix object will be instantiated and called as such:
    # obj = NumMatrix(matrix)
    # param_1 = obj.sumRegion(row1,col1,row2,col2)

## Tips ##

在初始化时就计算好前缀和，不要单独写函数实现，在计算sumRegion时每次反复计算，这样时间复杂度太高，会超时。

--------------------

A u t h o r : C h i e r Author: Chier Author:Chier

[20210302093029281.png_type_ZmFuZ3poZW5naGVpdGk_shadow_2_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDY4MjI5_size_10_color_FFFFFF_t_70]: /images/20221023/8870bb9cbeb0478690a1dda0402a4b02.png
[https_leetcode-cn.com_problems_range-sum-query-2d-immutable]: https://leetcode-cn.com/problems/range-sum-query-2d-immutable
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDY4MjI5_size_16_color_FFFFFF_t_70]: /images/20221023/178bff1fcc1241d9999c6e0dbd7dfdb9.png