矩阵置零

来自Leetcode第73题矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

统计行列

最开始是遍历写的，就不放上来了，统计需要置零的行与列，最后再统一置零

public void setZeroes(int[][] matrix) {
    int R = matrix.length;
    int C = matrix[0].length;
    List<Integer> rows = new ArrayList<>();
    List<Integer> cols = new ArrayList<>();

    // 标记要设为零的行和列
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (matrix[i][j] == 0) {
                rows.add(i);
                cols.add(j);
            }
        }
    }

    // 再次遍历数组，并使用行和列集更新元素。
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (rows.contains(i) || cols.contains(j)) {
                matrix[i][j] = 0;
            }
        }
    }
		
}

0(1)空间复杂度

来源题解

算法:

• 遍历整个矩阵，如果 cell[i][j] == 0 就将第 i 行和第 j 列的第一个元素标记。
• 第一行和第一列的标记是相同的，都是 cell[0][0]，所以需要一个额外的变量告知第一列是否被标记，同时用 cell[0][0] 继续表示第一行的标记。
• 然后，从第二行第二列的元素开始遍历，如果第 r 行或者第 c 列被标记了，那么就将 cell[r][c] 设为 0。这里第一行和第一列的作用就相当于方法一中的 row_set 和 column_set 。
• 然后我们检查是否 cell[0][0] == 0 ，如果是则赋值第一行的元素为零。
• 然后检查第一列是否被标记，如果是则赋值第一列的元素为零。

其他思路

来源题解

public void setZeroes(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return;
    }
    // 前一行为0标志
    boolean isLastRowZero = false;
    for (int i = 0; i < matrix.length; i ++) {
        // 当前行为0标志
        boolean isCurrRowZero = false;
        for (int j = 0; j < matrix[0].length; j ++) {
            if (matrix[i][j] == 0) {
                isCurrRowZero = true;
                // 纵向上一个值不是零，说明纵向第一次出现零，需要把纵向前面的值都置为零
                if (i > 0 && matrix[i - 1][j] != 0) {
                    for (int k = 0; k < i; k ++) {
                        matrix[k][j] = 0;
                    }
                }
            }
            // 纵向上一个值如果为零，则把纵向的零延伸到此行
            else if (i > 0 && matrix[i - 1][j] == 0){
                matrix[i][j] = 0;
            }
            
            // 如果上一行为零标志为真,则上一行这个位置置为零（纵向为零的判断在上面处理过，所以到这里才可以设置为0）
            if (isLastRowZero) {
                matrix[i - 1][j] = 0;
            }
        }
        isLastRowZero = isCurrRowZero;
    }

    // 处理最后一行为零的情况
    if (isLastRowZero) {
        for (int i = 0; i < matrix[0].length; i ++) {
            matrix[matrix.length - 1][i] = 0;
        }
    }
}