73. 矩阵置零

1. 题目简介

难度：中等，原题链接：73. 矩阵置零。

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

2. 问题分析

原矩阵里的一个 0 会使整行、整列清零，但新写入的 0 不应再触发清零。因此，需要先收集标记，再根据标记修改元素。

题目要求使用 原地 算法，可以借用首行和首列保存这些标记：

• matrix[i][0] == 0 表示第 i 行需要清零。
• matrix[0][j] == 0 表示第 j 列需要清零。

扫描内部区域时，每遇到 matrix[i][j] == 0，就把 matrix[i][0] 和 matrix[0][j] 设为 0。标记全部收集完后，再次扫描内部区域，只要对应行或列的标记为 0，就将当前元素清零。

首行、首列还承担了保存原始数据的作用，需要单独记录它们原来是否含有 0。代码在写标记之前，用 flag1 记录首列是否需要清零，用 flag2 记录首行是否需要清零，等内部区域处理完以后再使用这两个标志。

例如，只有 matrix[1][2] 原本为 0 时，标记会把 matrix[1][0] 和 matrix[0][2] 改成 0。这说明第 1 行和第 2 列需要清零，并不意味着首行、首列也要全部清零；两个独立标志就是为了保留这个区别。

3. 代码实现

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

        // 单独保存最上方的行是否需要全部都置零
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                flag1 = true;
            }
        }
        // 单独保存最左边的列是否需要全部都置零
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == 0) {
                flag2 = true;
            }
        }
        // 遍历矩阵，如果某一个元素为 0，那么就将该元素所在的行和列的第一个元素设置为 0
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        // 将需要置零的行和列的元素全部置零
        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;
                }
            }
        }
        // 将最上方的行全部置零
        if (flag1) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        // 将最左边的列全部置零
        if (flag2) {
            for (int i = 0; i < n; i++) {
                matrix[0][i] = 0;
            }
        }
    }
}

4. 复杂度分析

• 时间复杂度：O(m × n)，对 m 行、n 列的矩阵进行常数次扫描。
• 空间复杂度：O(1)，标记保存在原矩阵中，只额外使用两个布尔变量。

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明