利用前缀和计算二维矩阵子矩阵的和
- 作者简介:一名后端开发人员,每天分享后端开发以及人工智能相关技术,行业前沿信息,面试宝典。
- 座右铭:未来是不可确定的,慢慢来是最快的。
- 个人主页:极客李华-CSDN博客
- 合作方式:私聊+
- 这个专栏内容:用最低价格鼓励和博主一起在寒假打卡高频大厂算法题,连续一个月,提升自己的算法实力,为了算法比赛或者春招。
- 我的CSDN社区:https://bbs.csdn.net/forums/99eb3042821a4432868bb5bfc4d513a8
- 微信公众号,抖音,b站等平台统一叫做:极客李华,加入微信公众号领取各种编程资料,加入抖音,b站学习面试技巧,职业规划
二维矩阵在计算机科学中具有重要的地位,它们广泛用于图形处理、数据处理以及算法设计等领域。在处理二维矩阵时,经常需要计算子矩阵的和。例如,给定一个 n * n 的矩阵,我们可能需要计算其中所有i * i子矩阵的和。
解决方案
为了高效地计算子矩阵的和,可以利用前缀和技术。通过预处理得到一个与原矩阵相同大小的二维数组,用于存储矩阵中每个位置左上角子矩阵的和。然后,利用前缀和数组可以在常数时间内计算任意子矩阵的和。
前缀和公式原理
p
r
e
f
i
x
S
u
m
[
i
]
[
j
]
=
p
r
e
f
i
x
S
u
m
[
i
−
1
]
[
j
]
+
p
r
e
f
i
x
S
u
m
[
i
]
[
j
−
1
]
−
p
r
e
f
i
x
S
u
m
[
i
−
1
]
[
j
−
1
]
+
a
[
i
]
[
j
]
prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + a[i][j]
prefixSum[i][j]=prefixSum[i−1][j]+prefixSum[i][j−1]−prefixSum[i−1][j−1]+a[i][j]
示例代码
下面是利用前缀和技术计算二维矩阵子矩阵和的示例代码:文章来源:https://www.toymoban.com/news/detail-854851.html
#include <iostream>
using namespace std;
const int N = 4; // 矩阵的大小
int a[N + 1][N + 1] = {
{0, 0, 0, 0, 0}, // 增加一行一列用于边界处理
{0, 1, 0, 1, 0},
{0, 0, 1, 0, 1},
{0, 1, 0, 1, 0},
{0, 0, 1, 0, 1}
};
int main() {
// 计算前缀和
int prefixSum[N + 1][N + 1];
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + a[i][j];
}
}
// 遍历所有可能的 i x i 子矩阵
for (int i = 1; i <= N; ++i) {
for (int x1 = 1; x1 <= N - i + 1; ++x1) {
for (int y1 = 1; y1 <= N - i + 1; ++y1) {
int x2 = x1 + i - 1;
int y2 = y1 + i - 1;
// 计算子矩阵的和
int sum = prefixSum[x2][y2] - prefixSum[x2][y1 - 1] - prefixSum[x1 - 1][y2] + prefixSum[x1 - 1][y1 - 1];
cout << "以 (" << x1 << ", " << y1 << ") 为左上角," << i << "x" << i << " 子矩阵的和为: " << sum << endl;
}
}
}
return 0;
}
运行结果:文章来源地址https://www.toymoban.com/news/detail-854851.html
以 (1, 1) 为左上角,1x1 子矩阵的和为: 1
以 (1, 2) 为左上角,1x1 子矩阵的和为: 0
以 (1, 3) 为左上角,1x1 子矩阵的和为: 1
以 (1, 4) 为左上角,1x1 子矩阵的和为: 0
以 (2, 1) 为左上角,1x1 子矩阵的和为: 0
以 (2, 2) 为左上角,1x1 子矩阵的和为: 1
以 (2, 3) 为左上角,1x1 子矩阵的和为: 0
以 (2, 4) 为左上角,1x1 子矩阵的和为: 1
以 (3, 1) 为左上角,1x1 子矩阵的和为: 1
以 (3, 2) 为左上角,1x1 子矩阵的和为: 0
以 (3, 3) 为左上角,1x1 子矩阵的和为: 1
以 (3, 4) 为左上角,1x1 子矩阵的和为: 0
以 (4, 1) 为左上角,1x1 子矩阵的和为: 0
以 (4, 2) 为左上角,1x1 子矩阵的和为: 1
以 (4, 3) 为左上角,1x1 子矩阵的和为: 0
以 (4, 4) 为左上角,1x1 子矩阵的和为: 1
以 (1, 1) 为左上角,2x2 子矩阵的和为: 2
以 (1, 2) 为左上角,2x2 子矩阵的和为: 2
以 (1, 3) 为左上角,2x2 子矩阵的和为: 2
以 (2, 1) 为左上角,2x2 子矩阵的和为: 2
以 (2, 2) 为左上角,2x2 子矩阵的和为: 2
以 (2, 3) 为左上角,2x2 子矩阵的和为: 2
以 (3, 1) 为左上角,2x2 子矩阵的和为: 2
以 (3, 2) 为左上角,2x2 子矩阵的和为: 2
以 (3, 3) 为左上角,2x2 子矩阵的和为: 2
以 (1, 1) 为左上角,3x3 子矩阵的和为: 5
以 (1, 2) 为左上角,3x3 子矩阵的和为: 4
以 (2, 1) 为左上角,3x3 子矩阵的和为: 4
以 (2, 2) 为左上角,3x3 子矩阵的和为: 5
以 (1, 1) 为左上角,4x4 子矩阵的和为: 8
到了这里,关于利用前缀和计算二维矩阵子矩阵的和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!