LC 304. 二维区域和检索 - 矩阵不可变
题目描述
这是 LeetCode 上的 304. 二维区域和检索 - 矩阵不可变 ,难度为 中等。
给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2) 。
上图子矩阵左上角 (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
提示:
- 你可以假设矩阵不可变。
- 会多次调用 sumRegion 方法。
- 你可以假设 row1 ≤ row2 且 col1 ≤ col2 。
前缀和解法(二维)
真就是今天的「每日一题」呗 ~
这是一道「二维前缀和」的裸题。
「二维前缀和」解决的是二维矩阵中的矩形区域求和问题。
二维前缀和数组中的每一个格子记录的是「以当前位置为区域的右下角(区域左上角恒定为原数组的左上角)的区域和」
贴一张官解示意图,我觉得很清晰:
如果觉得不清晰,请将将 f[i][j] 理解成是以 (i, j) 为右下角,(0, 0) 为左上角的区域和。
因此当我们要求 (x1, y1) 作为左上角,(x2, y2) 作为右下角 的区域和的时候,可以直接利用前缀和数组快速求解:
sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]
再贴官解示意图(画图困难户在学做图了,别骂😢):
(x1, y1) == (row1, col1),(x2, y2) == (row2, col2)
代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class NumMatrix {
int[][] sum;
public NumMatrix(int[][] matrix) {
int n = matrix.length, m = n == 0 ? 0 : matrix[0].length;
// 与「一维前缀和」一样,前缀和数组下标从 1 开始,因此设定矩阵形状为 [n + 1][m + 1](模板部分)
sum = new int[n + 1][m + 1];
// 预处理除前缀和数组(模板部分)
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; 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 x1, int y1, int x2, int y2) {
// 求某一段区域和 [i, j] 的模板是 sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];(模板部分)
// 但由于我们源数组下标从 0 开始,因此要在模板的基础上进行 + 1
x1++; y1++; x2++; y2++;
return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}
}
- 时间复杂度:预处理前缀和数组需要对原数组进行线性扫描,复杂度为 $O(n m)$,计算结果复杂度为 $O(1)$。整体复杂度为 $O(n m)$
- 空间复杂度:$O(n * m)$
二维前缀和模板【重点】
下面重点分享下前缀和模板该如何记忆,其实很多模板都可以按照类似方式进行记忆。
虽然「二维前缀和」的模板相比「一维前缀和」的模板要长,但是逻辑是清晰的,可以现场推导。
当然也可以在理解的基础上,使用以下方式进行记忆:
1 |
|
最后
这是我们「刷穿 LeetCode」系列文章的第 No.304
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!