关于python:304二维区域和检索-矩阵不可变│leetcode

给定一个二维矩阵，计算其子矩形范畴内元素的总和，该子矩阵的左上角为 (row1, col1)，右下角为 (row2, col2)。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

上图子矩阵 (框中) 左上角 (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

提醒：你能够假如矩阵不可变。会屡次调用 sumRegion 办法。你能够假如 row1 ≤ row2 且 col1 ≤ col2。

以上是题目给出的所有内容，咱们能够先用最简略粗犷的办法写出一个解题办法。最简略粗犷的办法当然是循环遍历啦。

依据给出的子矩阵的左上角坐标和右下角坐标，循环遍历子矩阵中所有的点并相加，就是最终后果。上代码:

class NumMatrix:
    def __init__(self, matrix: list[list[int]]):
        self.matrix = matrix

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        sum_region = 0
        for row in range(row1, row2 + 1):  # 循环列(|)
            for col in range(col1, col2 + 1):  # 循环行(一)
                sum_region += self.matrix[row][col]
        return sum_region

这种办法在工夫复杂度和空间复杂度上都是 O(m*n)，甚至通过了提交，这道题完结，撒花。

然而这道题不能就此罢休，因为下面的解法尽管能够通过测试，然而应用的形式不是这道题想要考查的形式。在题目的提醒中，提到了会屡次调用 sumRegion() 办法。并且在给出的初始代码中也提醒到在测试时会先实例化对象，而后再执行办法。

依据以上的种种提醒，能够晓得这道题是想让咱们在实例化对象时就将二维数组进行预处理，而后在调用 sumRegion() 办法时能够更加高效的失去后果。

那么，热身完结，注释开始:

想一想，怎样才能在只给出子矩阵的左上角和右下角坐标的状况下最快失去子矩阵所有点之和呢?

我本人最先想到的办法是计算出矩阵中以后坐标与它同一行内之前所有坐标之和，这样在计算子矩阵坐标之和时，每行的坐标之和就能够通过简略的计算得出，而不是应用遍历累加。

如下图所示，新矩阵的每个坐标上的值都是与之同一行之前坐标的总和，那么在计算一行的子区间之和时，就能够通过右边界坐标 (图中蓝底红字) 的值减去左边界坐标再左移一位 (图中橙底红字) 的值算出。

计算子矩阵的坐标值之和，就能够遍历每行的值，而后累计。这种形式计算的工夫复杂度降到了 O(m)。代码如下:

class NumMatrix:
    def __init__(self, matrix: list[list[int]]):
        self.matrix, self.colSum = matrix, []
        for i in range(0, len(self.matrix)):
            self.colSum.append([])
            col_sum = 0
            for col in self.matrix[i]:
                col_sum += col
                self.colSum[i].append(col_sum)

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        sum_region = 0
        # 只须要循环列(|)
        for row in range(row1, row2 + 1):
            # 每行右坐标的值减去左坐标再左移一位的坐标的值
            # 因为左移后索引可能为 -1 所以要减少一个判断
            sum_region += self.colSum[row][col2] - (self.colSum[row][col1 - 1] if col1 != 0 else 0)
        return sum_region

运算效率相比最后的办法曾经大大提高了，然而这足够吗? 如果 sumRegion() 办法须要执行很屡次，那么总的工夫复杂度又达到了 O(m*n)，最后的办法的工夫复杂度就是 O(m*n*k)。那么，还有没有效率更高的办法呢?

答案是有，既然能够在每行的坐标中统计行 0 点坐标到以后坐标的累加值，那就能够提前计算出 (0, 0) 坐标到以后坐标的子矩阵累加值。计算子矩阵坐标值之和就只须要简略计算一次即可。

假如求左上角坐标 (A, B)，右下角坐标为 (C, D) 的子矩阵坐标值之和。当初 (C, D) 坐标的值曾经是 (0, 0) 到 (C, D) 坐标值之和了，那么这个值减去多余地位的值就是须要的答案了。那么减去一个 (0, 0) 到子矩阵右上角的坐标 (A - 1, D) 子矩阵(黄色局部 + 红色局部)，减去一个 (0, 0) 到子矩阵左下角的坐标 (C, B - 1) 子矩阵(紫色局部 + 红色局部)。这时发现两次减操作中有反复区域(红色局部)，那么还须要从新加上这部分，(0, 0) 到 子矩阵左上角的坐标 (A, B) 子矩阵(红色局部)。

计算公式为(坐标内的值是 (0, 0) 到以后点的子矩阵坐标值总和, 标记为 S):

子矩阵坐标值之和 = S(C, D) – S(A – 1, D) – S(C, B – 1) + S(A – 1, B – 1)

计算子矩阵坐标值之和问题解决了，然而有个前置问题没有解决，怎么失去每个坐标绝对于 (0, 0) 坐标之间的子矩阵坐标值之和。

总不能每个坐标点都进行一次循环列加循环行的二维遍历吧，这样做效率太低了。其实能够了解为子矩阵坐标值之和的反推。假如要失去 (A, B) 坐标绝对与 (0, 0) 坐标之间的子矩阵坐标值之和，那么能够将 (0, 0) 到 (A - 1, B) 子矩阵 (紫色局部 + 红色局部) 与 (0, 0) 到 (A, B - 1) 子矩阵 (黄色局部 + 红色局部) 相加，这时 (A - 1, B - 1) 子矩阵是被计算了两次，将这一子矩阵的值减去，最初再加上 (A, B) 的坐标值就是 (A, B) 坐标绝对于 (0, 0) 坐标之间的子矩阵坐标值之和。

计算公式为(坐标内的值是 (0, 0) 到以后点的子矩阵坐标值总和, 标记为 S):

坐标绝对原点的子矩阵坐标值之和 = (A, B) + S(A – 1, B) + S(A, B – 1) – S(A – 1, B – 1)

这时初始化计算所有坐标与原点的子矩阵坐标值之和的工夫复杂度为 O(n*m)，sumRegion() 办法的工夫复杂度为 O(1)，即便执行 N 此，总工夫复杂度也是 O(N). 代码如下:

class NumMatrix:
    def __init__(self, matrix: list[list[int]]):
        self.matrix, self.preSum = matrix, []
        for row in range(0, len(self.matrix)):
            self.preSum.append([])
            for col in range(0, len(self.matrix[row])):
                # 区域 A: (0, 0)->(A - 1, B)  区域 B: (0, 0)->(A, B - 1)  反复区域: (0, 0)->(A - 1, B - 1)
                # 有对索引值减操作, 要次要索引边界
                区域 A = self.preSum[row - 1][col] if row > 0 else 0
                区域 B = self.preSum[row][col - 1] if col > 0 else 0
                反复区域 = self.preSum[row - 1][col - 1] if (row > 0 and col > 0) else 0
                self.preSum[row].append(self.matrix[row][col] + 区域 A + 区域 B - 反复区域)

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        区域 A = self.preSum[row1 - 1][col2] if row1 > 0 else 0
        区域 B = self.preSum[row2][col1 - 1] if col1 > 0 else 0
        反复区域 = self.preSum[row1 - 1][col1 - 1] if (row1 > 0 and col1 > 0) else 0
        return self.preSum[row2][col2] - 区域 A - 区域 B + 反复区域

总结，通过一步步的优化，计算效率越来越高。我集体很喜爱这样的格调，先做出一个最简略粗犷然而效率不高的办法，而后再一步步优化。最初放出这三种办法的用时状况。

公众号 :「python 杂货铺」，专一于 python 语言及其相干常识。挖掘更多原创文章，期待您的关注。关注并回复「python」获取 python 相干材料。