304.二维区域和检索-矩阵不可变
给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。
示例
示例1：
给定 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 。
思路
无脑暴力解：
- 把
matrix中row1行到row2行的col1列到col2列相加并返回
- 当我们调用
sumRange()时，均需要循环n*m次
- 自信的点击提交！然后你就会发现会超出时间显示┭┮﹏┭┮
一维前缀和：
- 相加的环节我们放到构造函数中，这样的话我们在构造时只执行一遍
- 当我们调用
sumRange()时，只要执行n次便可
二维前缀和：
numMatrux每一个坐标的值都保存着(0,0)到当前坐标的矩形之和
白色矩形 = 整个矩形 - 粉色矩形 - 红色矩形 - 灰色矩形
也就是等于D坐标值 - B坐标值 - C坐标值 + A坐标值，其中减了2次灰色矩形，所以我们需要补回来
当我们调用 sumRange()时，只要执行1次便可
代码实现
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
class NumMatrix {
public:
vector<vector<int>> numMatrux;
NumMatrix(vector<vector<int>>& matrix) {
numMatrux = matrix;
}
int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for(int i = row1;i<=row2;i++){
for(int j = col1;j<=col2;j++){
sum += numMatrux[i][j];
}
}
return sum;
}
};
class NumMatrix {
public:
vector<vector<int>> numMatrux;
NumMatrix(vector<vector<int>>& matrix) {
if(matrix.empty()) return;
numMatrux.resize(matrix.size(),vector<int>(matrix[0].size()+1));
for(int i = 0;i<matrix.size();i++){
for(int j = 0;j<matrix[0].size();j++){
numMatrux[i][j+1] += matrix[i][j] + numMatrux[i][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for(int i = row1;i<=row2;i++){
sum += (numMatrux[i][col2+1]-numMatrux[i][col1]);
}
return sum;
}
};
class NumMatrix {
public:
vector<vector<int>> numMatrux;
NumMatrix(vector<vector<int>>& matrix) {
if(matrix.empty()) return;
numMatrux.resize(matrix.size()+1,vector<int>(matrix[0].size()+1));
for(int i = 0;i<matrix.size();i++){
for(int j = 0;j<matrix[0].size();j++){
numMatrux[i+1][j+1] =
numMatrux[i+1][j] +
numMatrux[i][j+1] -
numMatrux[i][j] +
matrix[i][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return
numMatrux[row2+1][col2+1] -
numMatrux[row1][col2+1] -
numMatrux[row2+1][col1] +
numMatrux[row1][col1];
}
};
|