73. 矩阵置零

题目链接：https://leetcode.cn/problems/set-matrix-zeroes/

代码

/**
 * 73. 矩阵置零
 * https://leetcode.cn/problems/set-matrix-zeroes/
 */

/**
 Do not return anything, modify matrix in-place instead.
 */
function setZeroes(matrix: number[][]): void {
    const rows = new Set<number>();
    const cols = new Set<number>();
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] === 0) {
                rows.add(i);
                cols.add(j);
            }
        }
    }
    for (const row of rows) {
        matrix[row].fill(0);
    }
    for (const col of cols) {
        for (let row = 0; row < matrix.length; row++) {
            matrix[row][col] = 0;
        }
    }
}

思路

使用两个集合分别记录需要置零的行和列：

1. 第一次遍历：遍历整个矩阵，将所有值为 0 的位置的行号和列号分别存入 rows 和 cols 集合中
2. 第二次遍历：遍历 rows 集合，将对应的行全部置零
3. 第三次遍历：遍历 cols 集合，将对应的列全部置零

这样可以在不影响判断的情况下完成矩阵置零操作。

• 时间复杂度 $O(m\times n)$，其中 $m$ 为矩阵行数，$n$ 为矩阵列数
• 空间复杂度 $O(m+n)$，需要额外的集合存储行号和列号