73 矩阵置零

一、题目

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

二、题解

2.1 使用额外数组（空间复杂度O(m+n)）

与其用矩阵的第一行和第一列来做标记（这容易引发覆盖和混乱），我们可以直接新建两个数组：

  1. 一个长度为 mm 的布尔数组 row，用来记录哪一行出现了 0。
  2. 一个长度为 nn 的布尔数组 col，用来记录哪一列出现了 0。

步骤：

  1. 第一次遍历（找 0）：遍历整个矩阵。如果发现 matrix[i][j] == 0，我们就把 row[i] 和 col[j] 都标记为 true。这就相当于把“这里有炸弹”的信息分别记录在两个独立的名单上。
  2. 第二次遍历（置 0）：再次遍历整个矩阵。对于每一个位置 (i, j)，只要查一下名单——如果 row[i] 是 true 或者 col[j] 是 true，说明它所在的行或列有 0，我们就直接把 matrix[i][j] 设为 0。
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        // 创建两个独立的标记数组
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];

        // 1. 第一次遍历：记录哪些行和哪些列包含 0
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }

        // 2. 第二次遍历：根据标记数组更新矩阵
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 只要当前行或当前列被标记过，就置为 0
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

时间复杂度：O(m×n)O(m \times n)

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

2.2 不使用额外数组（空间复杂度O(1)）

  1. 处理第一行和第一列的特殊情况：因为我们要用第一行和第一列做标记，所以先得用两个布尔变量 row0_flag 和 col0_flag 记录它们原本是否包含 0。
  2. 打标记：遍历矩阵其余部分（从第二行第二列开始，即 i = 1, j = 1）。如果遇到 matrix[i][j] == 0，就把对应的第一行 matrix[0][j] 和第一列 matrix[i][0] 设置为 0。
  3. 根据标记置零：再次遍历矩阵其余部分（从第二行第二列开始）。如果当前元素对应的第一行或第一列标记为了 0，就把当前元素 matrix[i][j] 置为 0。
  4. 最后处理第一行和第一列：根据第一步记录的 row0_flag 和 col0_flag，决定是否将整条第一行或第一列全部置为 0。
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        boolean row0_flag = false;
        boolean col0_flag = false;

        // 1. 判断第一行和第一列是否原本就包含 0
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                row0_flag = true;
                break;
            }
        }
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                col0_flag = true;
                break;
            }
        }

        // 2. 用第一行和第一列记录其他行和列是否包含 0
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0; // 标记对应的行首
                    matrix[0][j] = 0; // 标记对应的列首
                }
            }
        }

        // 3. 根据第一行和第一列的记录，置零其他内部元素
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // 4. 最后处理第一行和第一列
        if (row0_flag) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col0_flag) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

时间复杂度：O(m×n)O(m \times n)

空间复杂度：O(1)O(1)

评论