做建材加盟什么网站好,社保官方网站登录入口,长春有几个站可以坐火车,网络优化推广 网站开发建设题目
输入一个二维矩阵#xff0c;如何计算给定左上角坐标和右下角坐标的子矩阵的数字之和#xff1f;对于同一个二维矩阵#xff0c;计算子矩阵的数字之和的函数可能由于输入不同的坐标而被反复调用多次。例如#xff0c;输入图2.1中的二维矩阵#xff0c;以及左上角坐标…题目
输入一个二维矩阵如何计算给定左上角坐标和右下角坐标的子矩阵的数字之和对于同一个二维矩阵计算子矩阵的数字之和的函数可能由于输入不同的坐标而被反复调用多次。例如输入图2.1中的二维矩阵以及左上角坐标为21和右下角坐标为43的子矩阵该函数输出8。
分析
如果不考虑时间复杂度则采用蛮力法用两个嵌套的循环总是可以求出一个二维矩阵的数字之和。如果矩阵的行数和列数分别是m和n那么这种蛮力法的时间复杂度是Omn。
只是这个题目提到对于一个二维矩阵可能由于输入不同的坐标而反复求不同子矩阵的数字之和这说明应该优化求和的过程要尽可能快地实现子矩阵的数字求和。 阴影面积 黄色正方形面积 绿色正方行面积 - 红色长方形面积 - 蓝色长方形面积
因此可以在预处理阶段求出从左上角坐标为00到每个右下角坐标的子矩阵的数字之和。首先创建一个和输入矩阵大小相同的辅助矩阵sums该矩阵中的坐标ij的数值为输入矩阵中从左上角坐标00到右下角坐标ij的子矩阵的数字之和。
下面分析如何生成辅助矩阵sums即求得数组中的每个数字sums[i][j]。按照生成辅助矩阵sums的规则sums[i][j]的值等于输入矩阵中从左上角坐标为00到右下角坐标为ij的子矩阵的数字之和。可以把从左上角坐标为00到右下角坐标为ij的子矩阵的数字看成由两部分组成。第1部分是从左上角坐标为00到右下角坐标为i-1j的子矩阵该子矩阵的数字之和等于sums[i-1][j]。第2部分是输入矩阵中第i行中列号从0到j的所有数字。如果按照从左到右的顺序计算sums[i][j]则可以逐个累加第i行的数字从而得到子矩阵第2部分的数字之和。
解
public class Test {public static void main(String[] args) {int[][] nums {{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}};sums generateNumMatrix(nums);int result sumRegion(2, 1, 4, 3);System.out.println(result);}private static int[][] sums;public static int[][] generateNumMatrix(int[][] matrix) {if (matrix.length 0 || matrix[0].length 0) {return null;}int[][] sums new int[matrix.length 1][matrix[0].length 1];for (int i 0; i matrix.length; i) {int rowSum 0;for (int j 0; j matrix[0].length; j) {rowSum matrix[i][j];sums[i 1][j 1] sums[i][j 1] rowSum;}}return sums;}public static int sumRegion(int row1, int col1, int row2, int col2) {//return sums[row2][col2] sums[row1-1][col1-1] - sums[row1-1][col2] - sums[row2][col1-1];return sums[row2 1][col2 1] sums[row1][col1] - sums[row1][col2 1] - sums[row2 1][col1];}
}如果输入矩阵的行数和列数分别是m和n那么辅助数组sums的行数和列数分别为m1和n1这样只是为了简化代码逻辑。如果用公式sums[r2][c2]sums[r1-1][c2]-sums[r2][c1-1]sums[r1-1][c1-1]求解左上角坐标为r1c1、右下角坐标为r2c2的子矩阵的数字之和由于坐标值r1或c1有可能等于0因此r1-1或c1-1可能是负数不再是有效的数组下标。如果在矩阵的最上面增加一行最左面增加一列这样就不必担心出现数组下标为-1的情形。
