题目地址

https://leetcode-cn.com/problems/set-matrix-zeroes/

题目描述

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

示例 1:
输入:
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出:
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2:
输入:
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出:
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

进阶:
一个直接的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？

题解

边遍历边设置

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 0; i < m; ++ i) {
            for (int j = 0; j < n; ++ j) {
                if (matrix[i][j] == 0) {
                    fillZero(matrix, i, j);
                }
            }
        }
    }

    // 如果 [m, n] 位置的元素为 0，则将其所在行和列的所有元素都设为 0
    public void fillZero(int[][] matrix, int m, int n) {
        if (matrix[m][n] != 0) return;

        // [m, n] 所在列 n 设置为 0
        for (int i = 0; i < matrix.length; ++ i) {
            matrix[i][n] = 0;
        }

        // [m, n] 所在行 m 设置为 0
        for (int j = 0; j < matrix[0].length; ++ j) {
            matrix[m][j] = 0;
        }
    }
}

测试用例：

输入：
[[1,1,1],[1,0,1],[1,1,1]]

输出：
[[1,0,0],[0,0,0],[0,0,0]]

可以发现【边遍历边设置】会有一个问题，那就是不知道当前位置的 0 是输入中的状态还是后面设置的。
也就是说一个位置的 0 表示了两种状态：

• （1）输入时就为 0，因此需要将其所在行和列的所有元素都设为 0。
• （2）输入时不为 0，因此不需要进行第（1）步的操作。

先保存状态，再设置

保存输入中为 0 的点。

class Solution {
    public void setZeroes(int[][] matrix) {
        List<Integer> zeroPoints = new ArrayList<>();

        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 0; i < m; ++ i) {
            for (int j = 0; j < n; ++ j) {
                if (matrix[i][j] == 0) {
                    int point = i * n + j;
                    zeroPoints.add(point);
                }
            }
        }

        for (int point : zeroPoints) {
            int i = point / n;
            int j = point % n;
            fillZero(matrix, i, j);
        }
    }

    // 如果 [row, column] 位置的元素为 0，则将其所在行和列的所有元素都设为 0
    public void fillZero(int[][] matrix, int row, int column) {
        // [row, column] 所在列 column 设置为 0
        for (int i = 0; i < matrix.length; ++ i) {
            matrix[i][column] = 0;
        }

        // [row, column] 所在行 row 设置为 0
        for (int j = 0; j < matrix[0].length; ++ j) {
            matrix[row][j] = 0;
        }
    }
}

保存保存输入中为 0 的位置的行号和列号。

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        int[] rows = new int[m];
        int[] columns = new int[n];
        Arrays.fill(rows, 1);
        Arrays.fill(columns, 1);

        for (int i = 0; i < m; ++ i) {
            for (int j = 0; j < n; ++ j) {
                if (matrix[i][j] == 0) {
                    rows[i] = columns[j] = 0;
                }
            }
        }

        for (int i = 0; i < rows.length; ++ i) {
            if (rows[i] == 0) {
                fillRowZero(matrix, i);
            }
        }

        for (int i = 0; i < columns.length; ++ i) {
            if (columns[i] == 0) {
                fillColumnZero(matrix, i);
            }
        }
    }

    public void fillRowZero(int[][] matrix, int row) {
        // row 行设置为 0
        for (int column = 0; column < matrix[0].length; ++ column) {
            matrix[row][column] = 0;
        }
    }

    public void fillColumnZero(int[][] matrix, int column) {
        // column 列设置为 0
        for (int row = 0; row < matrix.length; ++ row) {
            matrix[row][column] = 0;
        }
    }
}

空间复杂度 O(m + n)。

使用矩阵第一行和第一列作为标记数组

class Solution {
    public void setZeroes(int[][] matrix) {
        boolean firstRowZero = false;
        boolean firstColumnZero = false;

        for (int row = 0; row < matrix.length; ++ row) {
            if (matrix[row][0] == 0) {
                firstColumnZero = true;
                break;
            }
        }
        for (int column = 0; column < matrix[0].length; ++ column) {
            if (matrix[0][column] == 0) {
                firstRowZero = true;
                break;
            }
        }


        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 0; i < m; ++ i) {
            for (int j = 0; j < n; ++ j) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }

        // 填充行
        for (int row = 1; row < matrix.length; ++ row) {
            if (matrix[row][0] == 0) {
                fillRowZero(matrix, row);
            }
        }
        // 填充列
        for (int column = 1; column < matrix[0].length; ++ column) {
            if (matrix[0][column] == 0) {
                fillColumnZero(matrix, column);
            }
        }

        // 最后填充第一行或者第一列
        if (firstRowZero) {
            fillRowZero(matrix, 0);
        }
        if (firstColumnZero) {
            fillColumnZero(matrix, 0);
        }
        
    }

    public void fillRowZero(int[][] matrix, int row) {
        // row 行设置为 0
        for (int column = 0; column < matrix[0].length; ++ column) {
            matrix[row][column] = 0;
        }
    }

    public void fillColumnZero(int[][] matrix, int column) {
        // column 列设置为 0
        for (int row = 0; row < matrix.length; ++ row) {
            matrix[row][column] = 0;
        }
    }
}

空间复杂度为 O(1)，因为只需要额外标记【第一行】和【第一列】是否为 0 即可。