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

• 一、题目描述
• 二、示例
• 三、难度
• 四、代码
• • Java版
  • • 4.1 法一：暴力法
    • 4.2 法二：数组不可变拓展
    • 4.3 法三：二维前缀和解法

一、题目描述

二、示例

三、难度

中等

四、代码

Java版

4.1 法一：暴力法

直接暴力解法，时间复杂度:O(n²)

package per.Kidd.demo;/ * @author Kidd * @create 2022-04-15 20:00 *//* *  304. 二维区域和检索 - 矩阵不可变 *      法一：暴力法 *    时间复杂度:O(n²) */public class NumMatrix {    private int[][] matrix;    public NumMatrix(int[][] matrix) { this.matrix = matrix;    }    public int sumRegion(int row1, int col1, int row2, int col2) { int sum = 0; for(int i = row1; i <= row2; ++i) {     for(int j = col1; j <= col2; ++j) {  sum += matrix[i][j];     } } return sum;    }    public static void main(String[] args) { int[][] matrixArray = {  {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 matrix = new NumMatrix(matrixArray); System.out.println(matrix.sumRegion(2,1,4,3));    }}

4.2 法二：数组不可变拓展

看作多个一维数组前缀和

package per.Kidd.demo;/* *  304. 二维区域和检索 - 矩阵不可变 *      法二：数组不可变拓展 */public class NumMatrix {    //记录每行前n个数之和    private int[][] preSumMatrix;    public void print() { for(int[] arr : preSumMatrix) {     for(int a : arr) {  System.out.print(a+" ");     }     System.out.println(); }    }    public NumMatrix(int[][] matrix) { preSumMatrix = new int[matrix.length + 1][matrix[0].length + 1]; //计算每行前n个数之和 for(int i = 0; i < matrix.length; ++i) {     for(int j = 0; j < matrix[0].length; ++j) {  preSumMatrix[i][j+1] = matrix[i][j] + preSumMatrix[i][j];     } }    }    public int sumRegion(int row1, int col1, int row2, int col2) { int sum = 0; for(int i = row1; i <= row2; ++i) {     sum += preSumMatrix[i][col2 + 1] - preSumMatrix[i][col1]; } return sum;    }    public static void main(String[] args) { int[][] matrixArray = {  {3,0,1,4},  {5,6,3,2},  {1,2,0,1},  {4,1,0,1},  {1,0,3,0} }; NumMatrix matrix = new NumMatrix(matrixArray); System.out.println(matrix.sumRegion(1, 2, 2, 3));    }}

4.3 法三：二维前缀和解法

时间复杂度O(nm)

package per.Kidd.demo;/ * @author Kidd * @create 2022-04-15 20:00 */public class NumMatrix {    //记录每行前n个数之和    private int[][] preSumMatrix;    public void print() { for(int[] arr : preSumMatrix) {     for(int a : arr) {  System.out.print(a+" ");     }     System.out.println(); }    }    public NumMatrix(int[][] matrix) { preSumMatrix = new int[matrix.length + 1][matrix[0].length + 1]; //计算每行前n个数之和 /*  *  初步思路：preSumMatrix[i][j]表示左上角(0,0)到右下角(i,j-1)元素之和，此preSumMatrix矩阵第一列和最后一行都为0  *      for(int i = 0; i < matrix.length; ++i) {  *    for(int j = 0; j < matrix[0].length; ++j) {  *//下标为0的列存放0 ，从下标为1的列开始存放元素之和  *      preSumMatrix[i][j+1] = preSumMatrix[i][j + 1] - preSumMatrix[i][j + 1];  *    }  *      }  *  *  因前缀和思想，行或列下标为0之前没有元素，所以和为0，将preSumMatrix[i][j]表示左上角(0,0)到右下角(i-1,j-1)元素之和  *  故将i,j从1开始，preSumMatrix矩阵的第一列和第一行都为0  */ for(int i = 1; i <= matrix.length; ++i) {     for(int j = 1; j <= matrix[0].length; ++j) {  // preSumMatrix[i+1][j+1]表示左上角(0,0)到右下角(i,j)元素之和  // 当前格子前缀和 = 上方的格子前缀和 + 左边的格子前缀和 - 左上角的格子前缀和 + 当前格子(值)【值是指原矩阵存放的值】  preSumMatrix[i][j] = preSumMatrix[i - 1][j] + preSumMatrix[i][j - 1] - preSumMatrix[i-1][j-1] + matrix[i-1][j-1];     } }    }    // 左上角(row1,col1)到右下角(row2,col2)元素之和    public int sumRegion(int row1, int col1, int row2, int col2) { // 因前缀和矩阵从 1 开始存储，原矩阵是从 0 开始存元素 return preSumMatrix[row2 + 1][col2 + 1] - preSumMatrix[row1][col2 + 1] - preSumMatrix[row2 + 1][col1] + preSumMatrix[row1][col1];    }    public static void main(String[] args) { int[][] matrixArray = {  {3,0,1,4},  {5,6,3,2},  {1,2,0,1},  {4,1,0,1},  {1,0,3,0} }; NumMatrix matrix = new NumMatrix(matrixArray); System.out.println(matrix.sumRegion(1, 2, 2, 3));//输出：6    }}