一起学习交流~

二维区域和检索 – 矩阵不可变

算法 laomuji 6个月前 (03-21) 446次浏览 已收录 0个评论

题目

给定一个二维矩阵 matrix,以下类型的多个请求:
计算其子矩形范围内元素的总和,该子矩阵的 左上角 为 (row1, col1) ,右下角 为 (row2, col2) 。
实现 NumMatrix 类:
NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。
示例 1:
输入:
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
[null, 8, 11, 12]
解释:
NumMatrix numMatrix = new NumMatrix([[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]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/range-sum-query-2d-immutable
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

/*
3 2 1
5 6 7
0 4 8

和
00-00 3
00-01 5
00-02 6
00-10 8
推测
00-11
由 当前值+左+上+左上 的和得到
结果应该为:
6+2+5+3=16

左前缀和为8 由00 和 10 的 3 + 5 = 8 得到
上前缀和为5 由00 和 01 的 3 + 2 = 5 得到
左上前缀和为3 由00 的 3 = 3 得到
当前值+左+上+左上的前缀和:
6+8+5+3=22
拆分一下前缀和
6+3+5+3+2+3 = 22
可以看到加了3次00的值3
而最终的结果应该只加1次00的值3,所以需要减少2次
也就是
prefix[i][j] = nums[i][j]+prefix[i][j-1]+prefix[i-1][j]+prefix[i-1][j-1]-2*prefix[i-1][j-1]
化简一下 就是
prefix[i][j] = nums[i][j]+prefix[i][j-1]+prefix[i-1][j]-prefix[i-1][j-1]
为了计算方便,将prefix增加一行和一列,设置为0,不用处理边界,下标从1开始
prefix[i][j] = nums[i-1][j-1]+prefix[i][j-1]+prefix[i-1][j]-prefix[i-1][j-1]

假设求区域和
11 - 22
22的前缀和为 36
来自于
8 + 20 + 24 - 16 = 36
而最终结果应该是25
全部区域是
3 2 1
5 6 7
0 4 8
而需要的区域是
6 7 
4 8
也就是
3  5  6
8  16 24
8  20 36
需要的是
16 24
20 36
也就是需要去掉
3 5 6 
8
8
36-8-6-3=19
8是3+5+0
6是3+2+1
3是3
拆分结果就是:
36-3-5-0-3-2-1-3
3只能减1次而这里减了3次
所以应该加上2次
36-8-6-3+2*3
化简为
36-8-6+3=25
区域
x1 y2 到 x2 y2
结果
prefix[x2][y2] - prefix[x2][y1-1] - prefix[x1-1][y2] + prefix[x1-1][y1-1]
prefix[x2][y2]-  prefix[x2][y1-1]-  prefix[x1-1][y2]+  prefix[x1-1][y1-1];
而存放的下标从1开始所以所有下标都应该+1
*/

代码

class NumMatrix {
private:
    vector<vector<int>>prefix;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        prefix.resize(m+1,vector<int>(n+1,0));
        for(int i =1;i<=m;i++){
            for(int j =1;j<=n;j++){
                prefix[i][j] = matrix[i-1][j-1]+prefix[i][j-1]+prefix[i-1][j]-prefix[i-1][j-1];
            }
        }
    }
    int sumRegion(int x1, int y1, int x2, int y2) {
        return prefix[x2+1][y2+1]-prefix[x2+1][y1+1-1]-prefix[x1+1-1][y2+1]+prefix[x1+1-1][y1+1-1];
    }
};
喜欢 (1)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论