Wednesday, March 13, 2013

[LeetCode] Set Matrix Zeros

Thought:
Constant space means we use the matrix itself to store the setting zero flag.

Code:
public class Solution {
    public void setZeroes(int[][] matrix) {
        
        int row = -1, col = -1, m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row = i;
                    col = j;
                    i = m;
                    j = n;
                }
            }
        }

        if (row == -1 && col == -1) return;
       
        for (int i = row; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][col] = 0;
                    matrix[row][j] = 0;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((matrix[row][j] == 0 && j != col) || (matrix[i][col] == 0 && i != row)) matrix[i][j] = 0;
            }
        }

        for (int i = 0; i < m; i++) matrix[i][col] = 0;
        for (int j = 0; j < n; j++) matrix[row][j] = 0;

    }
}

No comments:

Post a Comment