Dada una matriz de matriz 2D, encuentre la suma de los elementos dentro del rectángulo definido por su esquina superior izquierda (fila1, col1) y la esquina inferior derecha (fila2, col2).
Análisis
Dado que el supuesto es que hay muchas llamadas al método sumRegion, deberíamos usar algo de espacio extra para almacenar los resultados intermedios.
La solución es similar a otros problemas relacionados con la suma, como. La idea básica se demuestra en el siguiente ejemplo:
Aquí definimos una suma de matriz[][] que almacena el valor de la suma de (0,0) a la celda actual.
Solución Java
public class NumMatrix { int [][] sum; public NumMatrix(int[][] matrix) { if(matrix==null || matrix.length==0||matrix[0].length==0) return; int m = matrix.length; int n = matrix[0].length; sum = new int[m][n]; for(int i=0; i<m; i++){ int sumRow=0; for(int j=0; j<n; j++){ if(i==0){ sumRow += matrix[i][j]; sum[i][j]=sumRow; }else{ sumRow += matrix[i][j]; sum[i][j]=sumRow+sum[i-1][j]; } } } } public int sumRegion(int row1, int col1, int row2, int col2) { if(this.sum==null) return 0; int topRightX = row1; int topRightY = col2; int bottomLeftX=row2; int bottomLeftY= col1; int result=0; if(row1==0 && col1==0){ result = sum[row2][col2]; }else if(row1==0){ result = sum[row2][col2] -sum[bottomLeftX][bottomLeftY-1]; }else if(col1==0){ result = sum[row2][col2] -sum[topRightX-1][topRightY]; }else{ result = sum[row2][col2] -sum[topRightX-1][topRightY] -sum[bottomLeftX][bottomLeftY-1] +sum[row1-1][col1-1]; } return result; } } |
