C语言重构【304】二维区域和检索 - 矩阵不可变
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C语言重构【304】二维区域和检索 - 矩阵不可变，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1860字，纯文字阅读大概需要3分钟。
内容图文
文章目录
所有题目源代码：Git地址
题目
给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
上图子矩阵左上角 (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
方案：
- 大致思想就是先存好每个元素到0.0元素的和，然后要算的时候简单计算一下就行了，不用每个都遍历过去
class NumMatrix
{
public:
vector<vector<int>> mymatrix;
NumMatrix(vector<vector<int>> &matrix)
{
//意思是计算出某一点到（0,0）的和然后-上-左+左上
int row = matrix.size();
int col = matrix[0].size();
vector<vector<int>> tmp(row, vector<int>(col, 0));
mymatrix = tmp;
mymatrix[0][0] = matrix[0][0];
for (int i = 1; i < row; i++)
{
//init 第0列
mymatrix[i][0] = mymatrix[i - 1][0] + matrix[i][0];
// cout<<mymatrix[i][0]<<endl;
}
for (int i = 1; i < col; i++)
{
//init 第0行
mymatrix[0][i] = mymatrix[0][i - 1] + matrix[0][i];
// cout<<mymatrix[0][i]<<endl;
}
for (int i = 1; i < row; i++)
{
for (int j = 1; j < col; j++)
{
mymatrix[i][j] = mymatrix[i - 1][j] + mymatrix[i][j - 1] - mymatrix[i - 1][j - 1] + matrix[i][j];
// cout<<mymatrix[i][j]<<endl;
}
}
}
int sumRegion(int row1, int col1, int row2, int col2)
{
//=(r2,c2)-(r1-1,c2)-(r2,c1-1)+(r1-1,c1-1)
int res = mymatrix[row2][col2];
if (row1 > 0)
res -= mymatrix[row1 - 1][col2];
if (col1 > 0)
res -= mymatrix[row2][col1 - 1];
if (row1 > 0 && col1 > 0)
res += mymatrix[row1 - 1][col1 - 1];
return res;
}
};
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix* obj = new NumMatrix(matrix);
* int param_1 = obj->sumRegion(row1,col1,row2,col2);
*/
复杂度计算
- 时间复杂度：O(1):但是建造和矩阵的时候是n^2
- 空间复杂度：O(n^2)
内容总结
以上是互联网集市为您收集整理的C语言重构【304】二维区域和检索 - 矩阵不可变全部内容，希望文章能够帮你解决C语言重构【304】二维区域和检索 - 矩阵不可变所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】