当前位置: 首页 > article >正文

【数据结构-二维差分】力扣2536. 子矩阵元素加 1

给你一个正整数 n ,表示最初有一个 n x n 、下标从 0 开始的整数矩阵 mat ,矩阵中填满了 0 。

另给你一个二维整数数组 query 。针对每个查询 query[i] = [row1i, col1i, row2i, col2i] ,请你执行下述操作:

找出 左上角 为 (row1i, col1i) 且 右下角 为 (row2i, col2i) 的子矩阵,将子矩阵中的 每个元素 加 1 。也就是给所有满足 row1i <= x <= row2i 和 col1i <= y <= col2i 的 mat[x][y] 加 1 。
返回执行完所有操作后得到的矩阵 mat 。

示例 1:
在这里插入图片描述
输入:n = 3, queries = [[1,1,2,2],[0,0,1,1]]
输出:[[1,1,0],[1,2,1],[0,1,1]]
解释:上图所展示的分别是:初始矩阵、执行完第一个操作后的矩阵、执行完第二个操作后的矩阵。

  • 第一个操作:将左上角为 (1, 1) 且右下角为 (2, 2) 的子矩阵中的每个元素加 1 。
  • 第二个操作:将左上角为 (0, 0) 且右下角为 (1, 1) 的子矩阵中的每个元素加 1 。

示例 2:
在这里插入图片描述
输入:n = 2, queries = [[0,0,1,1]]
输出:[[1,1],[1,1]]
解释:上图所展示的分别是:初始矩阵、执行完第一个操作后的矩阵。

  • 第一个操作:将矩阵中的每个元素加 1 。

在这里插入图片描述

二维差分

class Solution {
public:
    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
        vector<vector<int>> diff(n+2, vector<int>(n+2));
        for(auto &query : queries){
            int r1 = query[0], c1 = query[1], r2 = query[2], c2 = query[3];
            diff[r1+1][c1+1]++;
            diff[r2+2][c1+1]--;
            diff[r1+1][c2+2]--;
            diff[r2+2][c2+2]++;
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1];
            }
        }
        
        diff.erase(diff.begin());
        diff.erase(diff.end());
        for(auto& row : diff){
            row.erase(row.begin());
            row.erase(row.end());
        }
        return diff;
    }
};

在二维差分中,我们要先求出二维的差分矩阵,然后在将其进行前缀和相加得到我们所想要的矩阵。在构造差分矩阵中,我们构造了一个大小(n+2) * (n+2)的矩阵。

有人会想问,为什么在一维差分中,差分只需要多1的空间,而在二维差分的矩阵中,我们有diff[r2+2][c2+2]++;,实际上是因为,我们在后面需要运用到前缀和来累加差分矩阵,而前缀和需要我们第0行和第0列都为0,用来辅助计算,而差分又使最后一行和最后一列多出来用来辅助差分计算,所以最后就需要多出两行和两列的空间。

计算完差分数组后,就计算差分的前缀和,就构成了我们答案需要的矩阵。但是前缀和运算后,由于矩阵的外面一圈都是用来辅助计算的,所以都要去掉。去掉外面一圈后,剩下的矩阵就是我们所需要的矩阵。


http://www.kler.cn/a/315185.html

相关文章:

  • 如何使用ffmpeg命令行进行录屏
  • 提取神经网络数学表达式
  • 虚拟机安装Ubuntu 24.04服务器版(命令行版)
  • 基于非时空的离身与反身智能
  • 类别变量分析——卡方独立性检验卡方拟合优度检验
  • 设计模式:工厂方法模式和策略模式
  • 插入与冒泡排序(C++)
  • C语言6大常用标准库 -- 4.<math.h>
  • Docker学习笔记(三)存储与卷
  • Vite + Vue + TypeScript 项目搭建总结
  • OpenMV学习第一步安装IDE_2024.09.20
  • 使用API有效率地管理Dynadot域名,为域名进行隐私保护设置
  • (C++23) expected 基础使用
  • hive-拉链表
  • 代码随想录算法训练营|151.翻转字符串里的单词 、卡码网:55.右旋转字符串
  • 分布式Redis(14)哈希槽
  • 深入理解Go并发编程:避免Goroutine泄漏与错误处理
  • C++_数据封装详解
  • 综述论文“Towards Personalized Federated Learning”分享
  • 研究生第一次刷力扣day1
  • 认识结构体
  • Docker笔记-Docker Dockerfile
  • 语言模型的在线策略提炼:从自我错误中学习
  • Redis数据结构之set
  • 音视频入门基础:AAC专题(8)——FFmpeg源码中计算AAC裸流AVStream的time_base的实现
  • Qt:静态局部变量实现单例(附带单例使用和内存管理)