企业官网建设流程全解析

• 教程
• 文档

本文是 LogicStack-LeetCode 仓库「刷穿 LeetCode」系列的第 73 篇，围绕 LeetCode 73. 矩阵置零 的题目与题解展开。文章以仓库中该题解的「模拟 + 原地」思路为骨架，完整继承题目描述、三条递进的空间优化路线与 Java/C++/Python/TypeScript 四语言实现，并结合仓库中同主题的 面试题 01.08 零矩阵（中等） 题解与 模拟算法索引 中相关题目的归类，补充逐行源码拆解、正确性论证、边界案例与调试验证方法，帮助读者彻底掌握「用原矩阵自身存储置零信息」的 O(1) 空间经典套路。

一、题目速览

题目：73. 矩阵置零（中等）Tag：「模拟」系列：LogicStack-LeetCode「刷穿 LeetCode」系列第 No.73 篇

给定一个m × n的矩阵，如果一个元素为0，则将其所在行和列的所有元素都设为0。题目强制要求使用「原地」算法，并给出三条递进的空间优化路线作为进阶挑战：

1. 使用O(m × n)的额外空间——直观但并非好的解决方案；
2. 使用O(m + n)的额外空间——简单的改进方案，但仍不是最好；
3. 仅使用常量空间（即O(1)额外空间）的解决方案。

数据范围提示：m = matrix.length，n = matrix[0].length，且1 <= m, n <= 200，矩阵元素取值在-2^31到2^31 - 1之间。

两个示例

示例 1

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]

矩阵中心的0使得第 1 行（下标从 0 计）与第 1 列全部变为0，其余元素保持不变。

示例 2

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

首行首列各有一个0，因此整行整列清零，同时元素5所在的列因首行存在0也被清零。

二、空间优化路线：从 O(m×n) 到 O(1)

题目前言指出，O(m × n)与O(m + n)的解法都“十分简单”，本质是两类直接的记录方式：

• O(m × n) 空间：复制一份同等大小的矩阵，在副本上根据原矩阵标记需要置零的位置，最后把副本写回原矩阵。缺点是额外空间与矩阵规模完全一致，完全没有必要；
• O(m + n) 空间：开辟与“行数量相等”的行标记数组、与“列数量相等”的列标记数组，先扫描一遍记录哪些行、哪些列需要被置零，再扫描一遍执行置零。

这一类「双标记数组」写法在仓库的 面试题 01.08 零矩阵 题解中给出了完整实现，是理解 O(1) 方案的重要前置参照：

// 摘自：LeetCode/面试题/面试题 01.08. 零矩阵（中等）.md class Solution { public void setZeroes(int[][] mat) { int n = mat.length, m = mat[0].length; boolean[] rows = new boolean[n], cols = new boolean[m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mat[i][j] == 0) rows[i] = cols[j] = true; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (rows[i] || cols[j]) mat[i][j] = 0; } } } }

这段代码时间复杂度为O(n × m)，空间复杂度为O(n + m)：第一遍扫描标记「需要被清零的行 / 列」，第二遍扫描利用标记完成置零，逻辑直接、不易出错。

而本题真正的考点，是如何把这两个长度分别为m与n的标记数组“塞进”原矩阵本身——也就是下面要重点展开的O(1) 空间解法。

三、O(1) 空间解法：三步走核心思路

O(1) 空间方案的核心矛盾在于：信息必须就地存储，但又不能污染后续判定所需的信息。解法将整个矩阵划分为「首行、首列」与「非首行首列」两块，分别处理，避免信息覆盖导致的错误传播。

1. 使用两个变量（r0 & c0），记录「首行 & 首列」是否该被置零

先用两个布尔变量r0、c0保存“首行是否含有 0”“首列是否含有 0”的结论。这是关键的一步：因为在后续步骤中，首行与首列会被当作标记存储区反复写入0，其原始信息会被覆盖，因此必须先把它们的“原始含零情况”备份出来。

boolean r0 = false, c0 = false; for (int i = 0; i < m; i++) { if (mat[i][0] == 0) { r0 = true; break; } } for (int j = 0; j < n; j++) { if (mat[0][j] == 0) { c0 = true; break; } }

注意：r0记录的是首列（第 0 列）是否含 0，c0记录的是首行（第 0 行）是否含 0，两者互相独立，命名与语义要一一对应，避免混淆。

2. 「非首行首列」的位置：存储 + 置零

这一步分为两个子阶段：

2.1 将置零信息存储到原矩阵

扫描「非首行首列」区域（下标从1开始），一旦发现mat[i][j] == 0，就把“第 i 行需要置零”的信息写到该行的最左方格子mat[i][0]，把“第 j 列需要置零”的信息写到该列的最上方格子mat[0][j]：

for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (mat[i][j] == 0) mat[i][0] = mat[0][j] = 0; } }

2.2 根据标记执行「非首行首列」置零

由于置零信息此时已经完整写入首行与首列，可以安全地对「非首行首列」区域执行清零：

// 按列清零：如果首行第 j 列被标记为 0，则整列（跳过首行）清零 for (int j = 1; j < n; j++) { if (mat[0][j] == 0) { for (int i = 1; i < m; i++) mat[i][j] = 0; } } // 按行清零：如果第 i 行的首列被标记为 0，则整行清零 for (int i = 1; i < m; i++) { if (mat[i][0] == 0) Arrays.fill(mat[i], 0); }

为什么这个顺序不会出错？因为 2.1 阶段在「非首行首列」区域发现的所有零，其置零信息都已经完整地沉淀到首行与首列；此时再去读取首行、首列作为“标记依据”，不会再被新的写零操作干扰（写零只发生在非首行首列区域）。换言之，信息从“非首行首列”单向流入“首行首列”，不存在回流污染。

3. 使用 r0 & c0，置零「首行 & 首列」

最后，用第 1 步备份的原始结论还原首行、首列的真实状态：

if (r0) for (int i = 0; i < m; i++) mat[i][0] = 0; if (c0) Arrays.fill(mat[0], 0);

• 若r0 == true（原首列含 0），把整列（第 0 列）清零；
• 若c0 == true（原首行含 0），把整行（第 0 行）清零。

至此，三步走全部完成，矩阵满足“含 0 元素所在行与列全部置零”的最终要求。

三步走顺序概览

四、四种语言实现与逐行要点

Java 版本

class Solution { public void setZeroes(int[][] mat) { int m = mat.length, n = mat[0].length; // 1. 扫描「首行」和「首列」记录「首行」和「首列」是否该被置零 boolean r0 = false, c0 = false; for (int i = 0; i < m; i++) { if (mat[i][0] == 0) { r0 = true; break; } } for (int j = 0; j < n; j++) { if (mat[0][j] == 0) { c0 = true; break; } } // 2.1 扫描「非首行首列」的位置，如果发现零，将需要置零的信息存储到该行的「最左方」和「最上方」的格子内 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (mat[i][j] == 0) mat[i][0] = mat[0][j] = 0; } } // 2.2 根据刚刚记录在「最左方」和「最上方」格子内的置零信息，进行「非首行首列」置零 for (int j = 1; j < n; j++) { if (mat[0][j] == 0) { for (int i = 1; i < m; i++) mat[i][j] = 0; } } for (int i = 1; i < m; i++) { if (mat[i][0] == 0) Arrays.fill(mat[i], 0); } // 3. 根据最开始记录的「首行」和「首列」信息，进行「首行首列」置零 if (r0) for (int i = 0; i < m; i++) mat[i][0] = 0; if (c0) Arrays.fill(mat[0], 0); } }

要点：Arrays.fill需要import java.util.Arrays；2.2 中“先按列清零、再按行清零”的顺序可以互换，因为两者读取的标记分别来自首行与首列，互不干扰。

C++ 版本

class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); bool r0 = false, c0 = false; for (int i = 0; i < m; i++) { if (matrix[i][0] == 0) { r0 = true; break; } } for (int j = 0; j < n; j++) { if (matrix[0][j] == 0) { c0 = true; break; } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0; } } for (int j = 1; j < n; j++) { if (matrix[0][j] == 0) { for (int i = 1; i < m; i++) matrix[i][j] = 0; } } for (int i = 1; i < m; i++) { if (matrix[i][0] == 0) fill(matrix[i].begin(), matrix[i].end(), 0); } if (r0) for (int i = 0; i < m; i++) matrix[i][0] = 0; if (c0) fill(matrix[0].begin(), matrix[0].end(), 0); } };

要点：fill(matrix[i].begin(), matrix[i].end(), 0)依赖<algorithm>头文件（使用std::fill），且传入的是vector<vector<int>>&引用，保证修改能写回原矩阵。

Python 版本

class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: m, n = len(matrix), len(matrix[0]) r0, c0 = False, False for i in range(m): if matrix[i][0] == 0: r0 = True break for j in range(n): if matrix[0][j] == 0: c0 = True break for i in range(1, m): for j in range(1, n): if matrix[i][j] == 0: matrix[i][0] = matrix[0][j] = 0 for j in range(1, n): if matrix[0][j] == 0: for i in range(1, m): matrix[i][j] = 0 for i in range(1, m): if matrix[i][0] == 0: matrix[i] = [0] * n if r0: for i in range(m): matrix[i][0] = 0 if c0: matrix[0] = [0] * n

要点：List[List[int]]需要from typing import List；函数直接原地修改matrix，不返回任何值（返回None）。Python 的matrix[i] = [0] * n会整体替换该行引用，同样能反映到外层列表。

TypeScript 版本

/** Do not return anything, modify matrix in-place instead. */ function setZeroes(matrix: number[][]): void { let m = matrix.length, n = matrix[0].length; let r0 = false, c0 = false; for (let i = 0; i < m; i++) { if (matrix[i][0] === 0) { r0 = true; break; } } for (let j = 0; j < n; j++) { if (matrix[0][j] === 0) { c0 = true; break; } } for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { if (matrix[i][j] === 0) matrix[i][0] = matrix[0][j] = 0; } } for (let j = 1; j < n; j++) { if (matrix[0][j] === 0) { for (let i = 1; i < m; i++) matrix[i][j] = 0; } } for (let i = 1; i < m; i++) { if (matrix[i][0] === 0) { for (let j = 0; j < n; j++) matrix[i][j] = 0; } } if (r0) for (let i = 0; i < m; i++) matrix[i][0] = 0; if (c0) for (let i = 0; i < n; i++) matrix[0][i] = 0; };

要点：TypeScript 版本在 2.2 阶段用显式双层循环代替fill类操作，思路完全一致；注意函数声明带有 JSDoc 注释「Do not return anything, modify matrix in-place instead」，明确这是原地修改、无返回值的接口约定。

四种语言实现遵循完全相同的三步走框架，仅语法层面不同，可作为「同一思路的多语言模板」互相参照。更多同类「模拟」题目的归类与索引见仓库的 模拟算法索引。

五、正确性论证与边界案例

为什么 O(1) 方案是对的？

可以用归纳的方式论证：

1. 信息完整性：任意非首行首列的0元素(i, j)，其“行置零需求”与“列置零需求”都被写入了mat[i][0]与mat[0][j]，因此 2.2 阶段依据首行首列标记就能完整覆盖所有需要清零的非边界元素；
2. 信息无污染：首行首列在作为标记区的同时，其原始含零状态已被r0/c0提前备份，第 3 步能还原正确的边界结果，不会因标记写入而丢失；
3. 覆盖完备：全体元素要么属于「非首行首列」（2.2 处理），要么属于「首行 / 首列」（第 3 步处理），不存在遗漏。

边界案例

• 矩阵只有一行（m = 1）：此时r0扫描首列只有mat[0][0]一个元素；2.1 阶段内层循环j从 1 开始，若该行中段含 0，会被记录到mat[0][j]；2.2 按列清零跳过首行，最终由c0决定是否整体清零，逻辑依然自洽；
• 矩阵只有一列（n = 1）：对称地，由r0承担最终决定权；
• 首行首列同时含 0：r0、c0都为true，第 3 步会把首行、首列全部清零，与直觉一致；
• 矩阵中无 0：两个标记循环与三步走都不会触发写零，矩阵保持原样；
• 含负值元素：判定条件是== 0的严格相等，负值、正值均不受影响（题给元素范围含负数）。

时空复杂度

• 时间复杂度：O(n × m)——每个元素在扫描与置零阶段最多被访问常数次；
• 空间复杂度：O(1)——除矩阵本身外，仅使用r0、c0两个布尔变量（以及循环下标等常数空间）。

六、如何本地调试与验证

仓库中的题解文档即为该题的完整学习材料（题目原文）。你可以按以下方式在本地复现与验证：

1. 任选一种语言，将对应Solution类 / 函数复制到本地（例如新建Solution.java/solution.py）；
2. 用两个官方示例构造测试数据：

示例 1：[[1,1,1],[1,0,1],[1,1,1]] → [[1,0,1],[0,0,0],[1,0,1]] 示例 2：[[0,1,2,0],[3,4,5,2],[1,3,1,5]] → [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

3. 打印调用前后的矩阵，人工比对每个位置的期望值；
4. 用第五节中的边界案例（单行、单列、全 0、无 0）做回归验证；
5. 在 LeetCode 页面选择对应语言提交，通过在线判题确认通过。

七、延伸思考

• 同类题：仓库中 面试题 01.08 零矩阵 与本题思路同源，其 O(m + n) 解法可作为本题 O(1) 方案的“直观版”前置铺垫，两篇对照阅读能更好地体会“标记数组下沉到原矩阵”的优化手法；
• 套路推广：本题是「用原数据结构自身承载标记信息」的典型例题，类似的思路还常见于「原地哈希」类问题——先备份关键信息，再把存储区复用为标记区，最后还原。掌握这一三步走框架，可以迁移到多种要求 O(1) 空间的矩阵与数组问题中；
• 与其他解法对比：如果面试中不要求 O(1) 空间，使用两个标记数组的写法（见第二节）更清晰、更不易错；只有在明确追求常量空间时才需要本题的三步走写法。理解两者的差异，才能在面试中根据要求灵活选择。

• 教程
• 文档