二维矩阵的前缀和+子矩阵的和-java

这篇具有很好参考价值的文章主要介绍了二维矩阵的前缀和+子矩阵的和-java。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二维矩阵的前缀和,我们可以通过求前缀和来把求二维矩阵的求某一块的和,从时间复杂度O(n^2)变成O(1)常数级,大大降低了时间复杂度

文章目录

前言

一、二维矩阵的前缀和应该怎么做?

1.引入一个二维数组

2.二维前缀和矩阵数组

3.推出二维矩阵前缀和的公式计算

3.1 代码如下

二.求子矩阵的和

1.算法思路

​编辑

2 子矩阵和公式推导

三、测试数据

1.代码如下(示例):

2.测试数据

2.1 测试数据如下

2.2运行结果如下

2.3样例结果解释

总结


前言

二维矩阵的前缀和,我们可以通过求前缀和来把求二维矩阵的求某一块的和,从时间复杂度O(n^2)变成O(1)常数级,大大降低了时间复杂度


提示:以下是本篇文章正文内容,下面案例可供参考

一、二维矩阵的前缀和应该怎么做?

1.引入一个二维数组

int[][] arr = {
0 0 0 0 0
0 1 7 2 4
0 3 6 2 8
0 2 1 2 3 
}

2.二维前缀和矩阵数组

二维矩阵前缀和和一维矩阵大同小异,我们可以定义矩阵前缀,是以右下角元素为主的矩阵的元素和。

我们可以一步一步的推出二维前缀矩阵里面各个位置的值。设置前缀和矩阵为s例如:我们求s[1][1]的值。

注:我们在初始位置多添加了一行、一列,因为原arr数组这些地方是没有值的

二维矩阵的前缀和+子矩阵的和-java,矩阵,线性代数,java

图2.1

二维矩阵的前缀和+子矩阵的和-java,矩阵,线性代数,java

图2.2

二维矩阵的前缀和+子矩阵的和-java,矩阵,线性代数,java

图2.3

二维矩阵的前缀和+子矩阵的和-java,矩阵,线性代数,java

 图2.4

即求图2.1黄色区域的面积=图2.2蓝色区域的面积+图2.3绿色区域的面积-图2.4紫色区域的面积(注因s[0][0]即图2.4紫色区域的面积被重复计算了)+arr[1][1]。

s[1][1] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + arr[1][1](注:里面的i=1,j=1)

3.推出二维矩阵前缀和的公式计算

由上述式子推出的s[1][1]的值我们可以推广到公式s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + arr[i][j] 

3.1 代码如下

int[][] s = new int[n+1][m+1];
        for(int i = 1;i <= n;i++ ){
            for(int j = 1;j <= m;j++){
                s[i][j] = s[i-1][j] + s[i][j-1]-s[i-1][j-1] + arr[i][j];
            }
        }

二.求子矩阵的和

1.算法思路

我们给定4个参数x1 y1 x2 y2,即求二维数组从arr[x1][y1]到arr[x2][y2]的区间和(图1.1蓝色区域的面积)

二维矩阵的前缀和+子矩阵的和-java,矩阵,线性代数,java

图 1.1

二维矩阵的前缀和+子矩阵的和-java,矩阵,线性代数,java

图1.2

二维矩阵的前缀和+子矩阵的和-java,矩阵,线性代数,java  

图 1.3

 二维矩阵的前缀和+子矩阵的和-java,矩阵,线性代数,java

 图1.4

二维矩阵的前缀和+子矩阵的和-java,矩阵,线性代数,java

图1.5 

我们可以用图1.2黄色区域的面积即s[x2][y2]-图1.3绿色区域的面积即s[x1-1][y2]-图1.4白色区域的面积s[x2][y1-1]+图1.5红色区域的面积s[x1-1][y1-1],就可以求出子矩阵的和。(注:跟我们推导二维前缀和数组的过程基本一样,同样是要加上被重复减去的部分即图1.5中的红色区域的面积)

2 子矩阵和公式推导

公式为 result = s[x2][y2]-s[x1-1][y2]-s[x2][y1-1] + s[x1-1][y1-1]

代码如下:

            int x1 = nextInt();
            int y1 = nextInt();
            int x2 = nextInt();
            int y2 = nextInt();
            pw.println(s[x2][y2]-s[x1-1][y2] - s[x2][y1-1]+s[x1-1][y1-1]);

三、测试数据

1.代码如下(示例):



import java.io.*;

public class 子矩阵的和 {
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static void main(String[] args) throws Exception{
        int n = nextInt();
        int m = nextInt();
        int q = nextInt();
        int[][] arr = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for(int j = 1;j <= m;j++){
                arr[i][j] = nextInt();
            }
        }
        int[][] s = new int[n+1][m+1];
        //构建前缀和矩阵
        for(int i = 1;i <= n;i++ ){
            for(int j = 1;j <= m;j++){
                s[i][j] = s[i-1][j] + s[i][j-1]-s[i-1][j-1] + arr[i][j];
            }
        }
        pw.println("------------------------");
        pw.println("前缀和矩阵如下:");
        for(int i = 1;i <= n;i++ ){
            for(int j = 1;j <= m;j++){
                pw.print(s[i][j]+" ");
            }
            pw.println();
        }
        pw.println("------------------------");
        //测试样例
        while(q-- > 0){
            int x1 = nextInt();
            int y1 = nextInt();
            int x2 = nextInt();
            int y2 = nextInt();
            pw.println(s[x2][y2]-s[x1-1][y2] - s[x2][y1-1]+s[x1-1][y1-1]);
        }
        pw.flush();
    }
    public static int nextInt()throws Exception{
        st.nextToken();
        return (int)st.nval;
    }
}

2.测试数据

2.1 测试数据如下

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

2.2运行结果如下

------------------------
前缀和矩阵如下:
1 8 10 14 
4 17 21 33 
6 20 26 41 
------------------------
17
27
21

2.3样例结果解释

17 = 1 + 7 + 3 + 6

27 = 3 + 6 + 2 + 8 +2 + 1 + 2 + 3

21 = 2 + 4 + 2 + 8 + 2 + 3 


总结

上述的重点还是在如何推导二维矩阵的前缀和矩阵,知道这个推导过程,对于后面的求子矩阵的和思路其实一样。文章来源地址https://www.toymoban.com/news/detail-843748.html

到了这里,关于二维矩阵的前缀和+子矩阵的和-java的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二维前缀和公式 AcWing 796. 子矩阵的和

    记住两个公式就行 不知道算难还是算简单,公式就是代码里面写的那样,完完全全公式,没有任何其他东西

    2024年02月19日
    浏览(10)
  • 线性代数本质系列(一)向量,线性组合,线性相关,矩阵

    本系列文章将从下面不同角度解析线性代数的本质,本文是本系列第一篇 向量究竟是什么? 向量的线性组合,基与线性相关 矩阵与线性相关 矩阵乘法与线性变换 三维空间中的线性变换 行列式 逆矩阵,列空间,秩与零空间 克莱姆法则 非方阵 点积与对偶性 叉积 以线性变换

    2024年02月04日
    浏览(13)
  • 线性代数:线性方程求解、矩阵的逆、线性组合、线性独立

    本文参考www.deeplearningbook.org一书第二章2.3 Identity and Inverse Matrices 2.4 Linear Dependence and Span 本文围绕 线性方程求解 依次介绍矩阵的逆、线性组合、线性独立等线性代数的基础知识点。 本文主要围绕求解线性方程展开,我们先把线性方程写出来,方程如下: 其中,是已知的;,

    2024年02月08日
    浏览(16)
  • 0203逆矩阵-矩阵及其运算-线性代数

    定义7 对于 n n n 阶矩阵A,如果有一个 n n n 阶矩阵B,使 A B = B A = E AB=BA=E A B = B A = E 则说矩阵A是可逆的,并把矩阵B称为A的逆矩阵,简称逆阵。 定理1 若矩阵A可逆,则 ∣ A ∣ ≠ 0 vert Avert not = 0 ∣ A ∣  = 0 证明: A 可逆,即有 A − 1 ,使得 A A − 1 = E ∣ A A − 1 ∣ = ∣ A

    2024年04月13日
    浏览(13)
  • 线性代数2:矩阵(1)

    目录 矩阵: 矩阵的定义: 0矩阵 方阵  同型矩阵: 矩阵相等的判定条件  矩阵的三则运算: 乘法的适用条件 矩阵与常数的乘法: 矩阵的乘法: 矩阵的乘法法则:  Note1:  Note2:  Note3:  向量与矩阵的关系: 转置矩阵:  矩阵多项式: 矩阵的重要性质:  性质2:  性质

    2024年02月08日
    浏览(27)
  • 投影矩阵推导【线性代数】

    如果两个向量垂直,那么满足。但如果两个向量不垂直,我们就将 b 投影到 a 上,就得到了二者的距离,我们也称为向量 b 到直线 a 的误差。这样就有出现了垂直:                (1) 投影向量 p 在直线上,不妨假设  ,那么误差 。带入式(1)中得到: 投影矩阵:  

    2024年02月06日
    浏览(20)
  • 线性代数——矩阵

    学习高等数学和线性代数需要的初等数学知识 线性代数——行列式 线性代数——矩阵 线性代数——向量 线性代数——线性方程组 线性代数——特征值和特征向量 线性代数——二次型 本文大部分内容皆来自李永乐老师考研教材和视频课。 从矩阵的转置章节到方阵和行列式

    2023年04月08日
    浏览(14)
  • 线性代数基础【2】矩阵

    一、基本概念 ①矩阵 像如下图示的为矩阵,记为A=(aij)m*n ②同型矩阵及矩阵相等 若A、B为如下两个矩阵 如果A和B的行数和列数相等,那么A和B为同型矩阵,且A和B的元素相等(即:aij=bij),则称A和B相等 ③伴随矩阵 设A为n阶矩阵(如上图所示),设A的行列式|A|,则A中aij的余子式为Mij,代数余

    2024年02月04日
    浏览(14)
  • 线性代数(七) 矩阵分析

    从性线变换我们得出,矩阵和函数是密不可分的。如何用函数的思维来分析矩阵。 通过这个定义我们就定义了矩阵序列的 收敛性 。 研究矩阵序列收敛性的常用方法,是用《常见向量范数和矩阵范数》来研究矩阵序列的极限。 长度是范数的一个特例。事实上,Frobenius范数对

    2024年02月08日
    浏览(11)
  • 线性代数-矩阵的本质

    线性代数-矩阵的本质

    2024年02月11日
    浏览(9)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包