LeetCode 73. 矩阵置零

约 6 分钟
文章信息 14 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 10-20 LeetCode 热题 100 面试经典 150 题 腾讯 字节 阿里 微软 美团 虾皮 猿辅导
标签
数组 哈希表 矩阵

题目描述

✅ 73. 矩阵置零

image-20260928220212765

image-20260928220212772

题意分析

以修改前的矩阵为准：某个元素为 0，就将它所在的整行、整列置为 0。新写入的 0 不能再触发清零，否则影响范围会不断扩大。题目要求原地修改，进阶要求额外空间为常数。

解法：第一行第一列原地标记

核心思路

[!blue]

直接的做法是用两个数组，分别记录哪些行、哪些列原本含有 0，再根据标记清零。要省掉这 $O(m+n)$ 的空间，可以借用矩阵的第一列记录行标记、第一行记录列标记：matrix[row][0] == 0 表示该行需要清零，matrix[0][col] == 0 表示该列需要清零。

第一行、第一列既是标记区，也有自己是否需要整行、整列清零的状态；共享的 matrix[0][0] 不能同时表达这两个独立条件。因此在写入标记前，用 firstRowZero、firstColZero 分别保存第一行、第一列原本是否含有 0。

接着只扫描内部区域。遇到原始的 0，就把它对应的行、列标记置为 0，内部元素保持不动，因此不会把新写入的标记误当作新的零源。边界上原有的 0 本身也是有效标记，不需要清除。扫描完成后，对每个非首行，行标记为 0 当且仅当该行原本含有 0；非首列的列标记同理。

再扫描内部，只要行标记或列标记为 0，就清零当前格。此时判断只读取标记区，修改内部不会污染后面的判断。最后按两个布尔值处理第一行、第一列，避免提前清空标记区而扩大清零范围。

若首行或首列的布尔值为假，不必整行或整列清零，但仍保留其中作为标记写入的 0：这些边界格所在的列或行原本就含有 0，最终也应该为 0。

解题步骤

  1. 在修改任何元素前，分别扫描第一行、第一列，记录 firstRowZero 和 firstColZero。
  2. 遍历 row >= 1、col >= 1 的内部区域。遇到 0，就令 matrix[row][0] = 0、matrix[0][col] = 0。
  3. 再遍历内部区域，行标记或列标记任意一个为 0，就将当前格置为 0。
  4. 若 firstRowZero 为真，将第一行清零；若 firstColZero 为真，将第一列清零。

题目保证矩阵非空。只有一行或一列时，内部遍历自然跳过，原始边界标志仍能正确决定最终结果。

代码实现

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

        for (int col = 0; col < n; col++) {
            // 先保存首行原始状态，之后它还要被用作列标记。
            firstRowZero |= matrix[0][col] == 0;
        }

        for (int row = 0; row < m; row++) {
            firstColZero |= matrix[row][0] == 0;
        }

        for (int row = 1; row < m; row++) {
            for (int col = 1; col < n; col++) {
                if (matrix[row][col] == 0) {
                    matrix[row][0] = 0;
                    matrix[0][col] = 0;
                }
            }
        }

        for (int row = 1; row < m; row++) {
            for (int col = 1; col < n; col++) {
                // 内部读取已完成的行列标记，首行首列此时还不能清空。
                if (matrix[row][0] == 0 || matrix[0][col] == 0) {
                    matrix[row][col] = 0;
                }
            }
        }

        // 内部处理完后，才按最初记录清理首行和首列。
        if (firstRowZero) {
            for (int col = 0; col < n; col++) {
                matrix[0][col] = 0;
            }
        }

        if (firstColZero) {
            for (int row = 0; row < m; row++) {
                matrix[row][0] = 0;
            }
        }
    }
}

func setZeroes(matrix [][]int) {
    m, n := len(matrix), len(matrix[0])
    firstRowZero, firstColZero := false, false

    for col := 0; col < n; col++ {
        // 先保存首行原始状态，之后它还要被用作列标记。
        firstRowZero = firstRowZero || matrix[0][col] == 0
    }
    for row := 0; row < m; row++ {
        firstColZero = firstColZero || matrix[row][0] == 0
    }

    for row := 1; row < m; row++ {
        for col := 1; col < n; col++ {
            if matrix[row][col] == 0 {
                matrix[row][0] = 0
                matrix[0][col] = 0
            }
        }
    }

    for row := 1; row < m; row++ {
        for col := 1; col < n; col++ {
            // 内部读取已完成的行列标记，首行首列此时还不能清空。
            if matrix[row][0] == 0 || matrix[0][col] == 0 {
                matrix[row][col] = 0
            }
        }
    }

    // 内部处理完后，才按最初记录清理首行和首列。
    if firstRowZero {
        for col := 0; col < n; col++ {
            matrix[0][col] = 0
        }
    }
    if firstColZero {
        for row := 0; row < m; row++ {
            matrix[row][0] = 0
        }
    }
}

复杂度分析

  • 时间复杂度：$O(mn)$，每个格子只被常数次访问。
  • 空间复杂度：$O(1)$，标记复用第一行、第一列，只额外使用两个布尔变量。

关键点总结

[!green]

  • 把行、列标记数组存进第一列、第一行，即可将额外空间降到 $O(1)$。
  • 标记阶段只改边界，内部清零阶段只读边界，保证后续判断始终依据原始零的位置。
  • 首行、首列的原始状态单独保存，内部处理完后才清理这两个边界。

易错点总结

[!yellow]

  • 发现 0 就立刻清空整行整列，会让新写入的 0 成为错误的清零依据。
  • 必须先保存首行、首列原始状态；写入标记后再判断，就分不清原始 0 和新标记。
  • 读取标记前不能清空第一行或第一列，否则会误判其他行列也需要清零。
  • 最后首行、首列的整行清零由两个布尔值决定，不能仅看 matrix[0][0]。
  • m 是行数，n 是列数；所有行循环与列循环都应使用各自的维度。

相似题目

题目 难度 关联与区别
289. 生命游戏 中等 同样要避免当前写入污染后续读取，可通过标记数组或原地编码区分旧状态与新状态。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/73238111
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！