Share my 4ms Solution, beats 96%


  • 1
    C
    public class NumMatrix {
      int[][] matrix;
      public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
        if (matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        for (int j = 1; j < matrix[0].length; j++) {
            matrix[0][j] += matrix[0][j - 1];
        }        
        for (int i = 1; i < matrix.length; i++) {
            int pre = 0;
            for (int j = 0; j < matrix[0].length; j++) {
                int temp = pre + matrix[i][j];
                matrix[i][j] += (pre + matrix[i - 1][j]);
                pre = temp;
            }
        }
      }
    
      public int sumRegion(int row1, int col1, int row2, int col2) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        if (row1 == 0 && col1 == 0) {
            return matrix[row2][col2];
        }
        if (row1 == 0) {
            return matrix[row2][col2] - matrix[row2][col1 - 1];
        }
        if (col1 == 0) {
            return matrix[row2][col2] - matrix[row1 - 1][col2];
        }
        return matrix[row2][col2] + matrix[row1 - 1][col1 - 1] - matrix[row2][col1 - 1] - matrix[row1 - 1][col2];
     }
    

    }


  • 0
    P

    why mine is cost 14ms ?

    private int[][] matrix = null ;
    public NumMatrix(int[][] matrix) {
        this.matrix = matrix ;
        for(int i=0;i<matrix.length;i++){
            	for(int j=0;j<matrix[0].length;j++){
            	this.matrix[i][j] =matrix[i][j] + (i>0?this.matrix[i-1][j]:0) + (j>0?this.matrix[i][j-1]:0)-(i*j>0?this.matrix[i-1][j-1]:0);
            	}
            }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return matrix[row2][col2]-(col1>0?matrix[row2][col1-1]:0)-(row1>0?matrix[row1-1][col2]:0)+(row1*col1>0?this.matrix[row1-1][col1-1]:0);
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.