二维前缀和:高效求解矩阵区域和问题
在处理二维矩阵时,频繁计算某一子矩阵的和是一个常见的操作。传统的做法是直接遍历该子矩阵,时间复杂度较高。当矩阵非常大且有大量的查询时,直接计算将变得低效。为了提高效率,我们可以通过 二维前缀和 技巧在常数时间内解决这个问题。
本文将通过一个具体的 Java 实现,介绍如何使用二维前缀和优化子矩阵求和问题。
关键是二维前缀和数组的构造,以及求解区域和的代码部分
测试链接:https://leetcode.cn/problems/range-sum-query-2d-immutable/
一、前缀和的概念
前缀和是解决区间和问题的经典技巧。在一维数组中,前缀和数组 prefixSum 用于存储从数组开头到当前位置的累加和,这样我们可以在 O(1) 时间内查询任意区间 [l, r] 的和。
二维前缀和的思想类似,它在二维矩阵上扩展了前缀和的概念。给定一个 m x n 的矩阵 matrix,二维前缀和数组 sum 中的元素 sum[i][j] 表示从左上角 (0, 0) 到 (i-1, j-1) 的所有矩阵元素的和。通过构造这个前缀和数组,我们能够在常数时间内查询任意子矩阵的元素和。
二、二维前缀和的计算
2.1 二维前缀和的构建
对于一个 m x n 的矩阵 matrix,我们定义一个同样大小的前缀和数组 sum,其中 sum[i][j] 表示从 (0, 0) 到 (i-1, j-1) 的矩阵元素和。构造 sum[i][j] 的公式如下:
sum[i][j] = matrix[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]
matrix[i-1][j-1]:当前矩阵元素。sum[i-1][j]:上方区域的和。sum[i][j-1]:左侧区域的和。sum[i-1][j-1]:左上角区域重复计算的部分,需要减去。
这样通过累加计算每个位置的前缀和,最终可以在常数时间内求出任意子矩阵的和。
2.2 子矩阵和的查询
通过上述方式构造的二维前缀和数组,可以快速计算任意子矩阵的元素和。给定一个矩阵区域的左上角 (row1, col1) 和右下角 (row2, col2),其和可以通过以下公式计算:
sumRegion(row1, col1, row2, col2) = sum[row2+1][col2+1]- sum[row1][col2+1]- sum[row2+1][col1]+ sum[row1][col1]
三、Java 实现
以下是使用二维前缀和优化矩阵区域和查询的 Java 实现。我们将使用 NumMatrix 类来实现:
public class NumMatrix {private int[][] sum;// 构造函数:计算二维前缀和public NumMatrix(int[][] matrix) {int n = matrix.length;int m = matrix[0].length;sum = new int[n + 1][m + 1]; // 创建一个多出一行一列的前缀和数组// 填充前缀和数组for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {sum[i][j] = matrix[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];}}}// 查询子矩阵的和public int sumRegion(int row1, int col1, int row2, int col2) {row1++;col1++;row2++;col2++;return sum[row2][col2] - sum[row1 - 1][col2] - sum[row2][col1 - 1] + sum[row1 - 1][col1 - 1];}public static void main(String[] args) {// 示例矩阵int[][] matrix = {{3, 2, 1, 4},{1, 5, 3, 2},{4, 2, 2, 1},{7, 4, 3, 5}};// 创建 NumMatrix 对象NumMatrix numMatrix = new NumMatrix(matrix);// 查询子矩阵 (1,1) 到 (2,2) 的和System.out.println(numMatrix.sumRegion(1, 1, 2, 2)); // 输出:15}
}
3.1 代码分析
-
构造函数:
NumMatrix(int[][] matrix)用来构造二维前缀和数组sum。首先,构造一个大小为(n+1) x (m+1)的数组,额外的行和列用于处理边界问题。然后通过双重循环填充sum数组,利用之前的公式逐步计算前缀和。 -
sumRegion方法:sumRegion(int row1, int col1, int row2, int col2)用于查询子矩阵(row1, col1)到(row2, col2)的和。通过前缀和的计算公式,能够在常数时间内返回结果。 -
主函数:在
main方法中,我们定义了一个matrix,并创建了NumMatrix对象来处理前缀和的计算。然后调用sumRegion方法查询从(1,1)到(2,2)的子矩阵和,输出为15。
四、时间复杂度
- 前缀和数组的构造:构造二维前缀和数组的时间复杂度是
O(m * n),其中m和n分别是矩阵的行数和列数。 - 查询子矩阵和:查询的时间复杂度是
O(1),因为我们只需要做常数次的数组访问和加减操作。
五、应用场景
二维前缀和特别适用于以下场景:
- 静态矩阵区域求和:如果我们需要对矩阵中多个子矩阵进行求和,二维前缀和能够显著减少查询时间。
- 优化算法中的区间求和:在一些动态规划或分治算法中,二维前缀和可以高效地处理二维区间和查询。
相关文章:
二维前缀和:高效求解矩阵区域和问题
在处理二维矩阵时,频繁计算某一子矩阵的和是一个常见的操作。传统的做法是直接遍历该子矩阵,时间复杂度较高。当矩阵非常大且有大量的查询时,直接计算将变得低效。为了提高效率,我们可以通过 二维前缀和 技巧在常数时间内解决这个…...
鸢尾花书《编程不难》02---学习书本里面的三个案例
文章目录 1.引言2.第一个例子---模拟硬币的投掷结果3.第二个例子---混合两个一元高斯分布的随机数4.第三个例子---线性回归的作图5.关于书中的问题的解决方案 1.引言 今天的这个文章主要是阅读学习鸢尾花书系列的第一本《编程不难》,今天主要是记录下书里面的两个例…...
MySQL(高级特性篇) 13 章——事务基础知识
一、数据库事务概述 事务是数据库区别于文件系统的重要特性之一 (1)存储引擎支持情况 SHOW ENGINES命令来查看当前MySQL支持的存储引擎都有哪些,以及这些存储引擎是否支持事务能看出在MySQL中,只有InnoDB是支持事务的 &#x…...
CSS Display属性完全指南
CSS Display属性完全指南 引言核心概念常用display值详解1. block(块级元素)2. inline(行内元素)3. inline-block(行内块级元素)4. flex(弹性布局)5. grid(网格布局&…...
【机器学习篇】K-Means 算法详解:从理论到实践的全面解析
网罗开发 (小红书、快手、视频号同名) 大家好,我是 展菲,目前在上市企业从事人工智能项目研发管理工作,平时热衷于分享各种编程领域的软硬技能知识以及前沿技术,包括iOS、前端、Harmony OS、Java、Python等…...
IntelliJ IDEA远程开发代理远程服务器端口(免费内网穿透)
IntelliJ IDEA远程开发代理远程服务器端口(免费内网穿透)(JetBrains家的其他IDE应该也支持) 之前看到宇宙第一IDE VS Code好像默认代理了远程的端口,但是一直没找到IDEA的同类功能,这次终于发现了 以Intell…...
内核定时器3-用户空间定时器
用户空间定时器与内核定时器的关系 虽然用户空间定时器和内核定时器在实现上各自独立,但用户空间定时器通常依赖于内核定时器提供的基础设施。以下是具体关系: 依赖性 用户空间定时器的实现基于内核定时器。 例如,POSIX 定时器使用内核的 h…...
C++ 字面量深度解析:从基础到实战进阶
在 C 开发中,字面量(Literal)不仅是基础语法的一部分,更是提升代码可读性、安全性和性能的关键工具。本文将深入探讨 C 字面量的高级特性、最新标准支持(C11/14/17/20)以及实际开发中的应用技巧,…...
论文paper(更新...)
目录 是否rebuttal?rebuttal 技巧 是否rebuttal? 如果不rebuttal 肯定会拒稿,编辑也会给审稿人发信息,如下: Comment: Thanks for your efforts in reviewing this paper. The authors have neither submitted a rebu…...
变形金刚多元宇宙
1 涉及的公司 1.1 孩之宝HasBro 孩之宝与Takara签订协议后,孩之宝开始使用Takara的专利进行研发。 1.2 日本特佳丽Takara公司 特佳丽Takara Diaclone可变形恐龙的机器人玩具 Microman可变形汽车的机器人玩具 1.3 日本东映TOEI ANIMTION 1.4 美国漫威 为了推广玩具…...
HTTP协议的无状态和无连接
无连接 ①无连接的含义 这里所说的无连接并不是指不连接,客户与服务器之间的HTTP连接是一种一次性连接,它限制每次连接只处理一个请求,当服务器返回本次请求的应答后便立即关闭连接,下次请求再重新建立连接。这种一次性连接主要考…...
ASP.NET代码审计 SQL注入篇(简单记录)
sql注入,全局搜索 Request QueryString ToString() select select * aspx是设计页面,而aspx.cs是类页面,也就是说设计页面用到的类信息在这个页面里面,其实就是把设计和实现分离开来。 源码 using System; using System.Collect…...
毫秒级响应的VoIP中的系统组合推荐
在高并发、低延迟、毫秒级响应的 VoIP 场景中,选择合适的操作系统组合至关重要。以下是针对 Ubuntu linux-lowlatency、CentOS Stream kernel-rt 和 Debian 自定义 PREEMPT_RT 的详细对比及推荐: 1. 系统组合对比 特性Ubuntu linux-lowlatencyCentO…...
w186格障碍诊断系统spring boot设计与实现
🙊作者简介:多年一线开发工作经验,原创团队,分享技术代码帮助学生学习,独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取,记得注明来意哦~🌹赠送计算机毕业设计600个选题excel文…...
shell -c
个人博客地址:shell -c | 一张假钞的真实世界 shell -c {string}:表示命令从-c后的字符串读取。在需要使用管道或者重定向需要sudo时很有用,如下: $ sudo find ../*/exportFiles -mtime 15 -name "*" | xargs -I {} r…...
(笔记+作业)书生大模型实战营春节卷王班---L1G3000 浦语提示词工程实践
学员闯关手册:https://aicarrier.feishu.cn/wiki/QtJnweAW1iFl8LkoMKGcsUS9nld 课程视频:https://www.bilibili.com/video/BV13U1VYmEUr/ 课程文档:https://github.com/InternLM/Tutorial/tree/camp4/docs/L0/Python 关卡作业:htt…...
文献学习笔记:中风醒脑液(FYTF-919)临床试验解读:有效还是无效?
【中风醒脑液(FYTF-919)临床试验解读:有效还是无效?】 在发表于 The Lancet (2024 年 11 月 30 日,第 404 卷)的临床研究《Traditional Chinese medicine FYTF-919 (Zhongfeng Xingnao oral pr…...
Chapter2 Amplifiers, Source followers Cascodes
Chapter2 Amplifiers, Source followers & Cascodes MOS单管根据输入输出, 可分为CS放大器, source follower和cascode 三种结构. Single-transistor amplifiers 这一章学习模拟电路基本单元-单管放大器 单管运放由Common-Source加上DC电流源组成. Avgm*Rds, gm和rds和…...
从0开始使用面对对象C语言搭建一个基于OLED的图形显示框架(绘图设备封装)
目录 图像层的底层抽象——绘图设备抽象 如何抽象一个绘图设备? 桥接绘图设备,特化为OLED设备 题外话:设备的属性,与设计一个相似函数化简的通用办法 使用函数指针来操作设备 总结一下 图像层的底层抽象——绘图设备抽象 在…...
Android学习19 -- 手搓App
1 前言 之前工作中,很多时候要搞一个简单的app去验证底层功能,Android studio又过于重型,之前用gradle,被版本匹配和下载外网包折腾的堪称噩梦。所以搞app都只有找应用的同事帮忙。一直想知道一些简单的app怎么能手搓一下&#x…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...
