矩阵置零
Set Matrix Zeroes
如果某个元素是 0，就把它所在的整行和整列都置零，要求原地修改。
在力扣中练习题目描述
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 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]]
提示：
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-231 <= matrix[i][j] <= 231 - 1
进阶：
- 一个直观的解决方案是使用
O(mn)的额外空间，但这并不是一个好的解决方案。 - 一个简单的改进方案是使用
O(m + n)的额外空间，但这仍然不是最好的解决方案。 - 你能想出一个仅使用常量空间的解决方案吗？
解题思路
首行首列 · 原地标记
拿第一行和第一列当两个标记数组，额外空间压到 O(1)
最直接的做法是先把所有 0 的位置记下来，再统一置零；问题是要额外的 m + n 空间。能不能借矩阵自己的格子做标记？可以：把第 i 行的标记写进 matrix[i][0]，把第 j 列的标记写进 matrix[0][j]。
难点在于第一行、第一列本身就是数据：它们既当标记数组，又可能被清空。所以先用 firstRow、firstCol 两个布尔量记住它们原本有没有 0，再放心覆盖。
原始矩阵里 (0,0) 就是 0；第一行和第一列既可能被用来标记，也可能是要清空的数据。
扫描内部从 i = 1, j = 1 开始，避免把标记位当成新的 0 反复传播。内部清完后，最后再根据两个布尔量处理第一行和第一列。
第 1 行行首是标记 0，整行内部被置零；注意 (1,2) 本来就是 0。
- i
- 1
本主例的 (0,0) 本身是 0，首行和首列都含 0；如果漏掉布尔量，首行首列会被标记逻辑误判或在错误的时间清空。
易错点
- 内部扫描从 0 开始：刚写下的行首标记会被当成新的 0，整行被误清。
- 先清首行首列再清内部：列标记提前消失，后面的列漏清。
- 只用一个布尔量：首行和首列的原始状态是两件独立的事。
行列数组 · 额外空间
先统计哪几行、哪几列要清，再统一写入
最容易写对，但需要 O(m+n) 额外空间；主解法用首行首列替代这两个数组。
开两个布尔数组 rowZero、colZero，第一遍记录哪些行、哪些列出现过 0，第二遍按记录统一置零。
它把“标记”和“数据”彻底分开，不存在首行首列被覆盖的问题，代码也最短。代价是 O(m+n) 的额外空间。
当矩阵非常大、内存紧张时，这个方案不满足原地要求；但它是理解原地优化之前最好的跳板：主解法不过是把这两个数组塞进了矩阵的首行首列。
- 1建立 rowZero 与 colZero。
- 2第一次遍历，遇到 0 就标记所在行和列。
- 3第二次遍历，按标记置零。
易错点
- 边读边置零：新产生的 0 会继续扩散，必须分两遍。
- 只标记行或只标记列，另一个方向会漏。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
matrix = [[0,2,3,4],[5,6,0,8],[9,10,11,12]]原始矩阵里 (0,0) 就是 0；第一行和第一列既可能被用来标记，也可能是要清空的数据。
查看 C++ 代码
延伸阅读
- 原地标记的核心是“借用输入自身的空间”，但要先处理被借用的那部分数据。
- 同类思路：轮转数组借用反转，缺失的第一个正数借用下标位置。