73.矩阵置零

原地标记

题目要求原地完成，因此不能直接额外开两个数组记录哪些行和哪些列要置零。一个常见做法是把第一行和第一列当作标记位来使用。

先单独记录第一行是否原本就含有 $0$，记为 firstRow。随后遍历除第一行之外的所有位置，如果 matrix[i][j] == 0，就把 matrix[i][0] 和 matrix[0][j] 置为 $0$，分别表示第 $i$ 行和第 $j$ 列最终都要变成 $0$。

最后再倒序遍历整个矩阵。对于非第一行元素，只要所在行或所在列的标记为 $0$，就将当前位置置零；对于第一行，则根据 firstRow 决定是否全部置零。之所以倒序处理，是为了避免过早修改第一行和第一列中的标记，影响后续判断。

时间复杂度 $O(mn)$

空间复杂度 $O(1)$

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int firstRow = 1;
        for (int j = 0; j < n; ++j) {
            firstRow = matrix[0][j] == 0 ? 0 : firstRow;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (i == 0) {
                    if (firstRow == 0) {
                        matrix[i][j] = 0;
                    }
                } else {
                    if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                        matrix[i][j] = 0;
                    }
                }
            }
        }
    }
}