京公网安备11010502063487号给定一个 m × n 的矩阵，如果某个元素是 0，就把它所在的整行和整列都设为 0，要求原地操作。最容易想到的做法是用两个集合记下所有含 0 的行和列，最后统一清零，额外空间 O(m + n)。进阶要求是只用 O(1) 额外空间：把矩阵自己的第一行和第一列当作"这一行要清零""这一列要清零"的标记。这样做的难点在于第一行和第一列本身也可能含有原来的 0，需要单独记录。本文用真实数据展示两个典型的错误各自会错多少，给出五种语言的实现，并把标记和清零的两个阶段做成分步演示。
完整题目见官方页面（链接在文末）。基准解就是上面那个用集合记下含 0 的行和列的做法，额外空间 O(m + n)，与 O(1) 空间的标记法是两种独立的写法。一共 12 组用例，覆盖：官方两个示例、单个格子（0 或非 0）、单行、单列、0 在第一行或第一列、0 在最后一个格子、多个 0：
输入 [[[1,1,1],[1,0,1],[1,1,1]]] 输出 [[1,0,1],[0,0,0],[1,0,1]] 输入 [[[0,1,2,0],[3,4,5,2],[1,3,1,5]]] 输出 [[0,0,0,0],[0,4,5,0],[0,3,1,0]] 输入 [[[1]]] 输出 [[1]] 输入 [[[0]]] 输出 [[0]] 输入 [[[1,0]]] 输出 [[0,0]] 输入 [[[1],[0]]] 输出 [[0],[0]]
如果一边扫描一边发现 0 就立刻把它的行和列清零，之后扫描到的、刚被清出来的 0，会被误当成原来就有的 0，再次清零它们的行列，最终会清掉不该清的元素。下面是真实结果：
# 发现 0 就立刻清零行和列的写法（新产生的 0 也被当成原来的 0） [[1, 1, 1], [1, 0, 1], [1, 1, 1]]: 立刻清零 -> [[1, 0, 0], [0, 0, 0], [0, 0, 0]] solve -> [[1, 0, 1], [0, 0, 0], [1, 0, 1]] [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]: 立刻清零 -> [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] solve -> [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]] [[1, 2, 3], [4, 5, 6]]: 立刻清零 -> [[1, 2, 3], [4, 5, 6]] solve -> [[1, 2, 3], [4, 5, 6]] 随机 20000 个矩阵：该写法与正确答案不同的有 8951 个（44.8%）
官方示例 [[1, 1, 1], [1, 0, 1], [1, 1, 1]] 应该只清零第 1 行和第 1 列，得到 [[1, 0, 1], [0, 0, 0], [1, 0, 1]]，而这种写法把整个矩阵几乎全清成了 0（只剩最左上角的 1）。第二个示例更严重：整个矩阵全被清零。第三行矩阵没有 0，两种写法一致。随机的 20000 个矩阵里，这种写法出错的有 8951 个，占 44.8%。所以必须先把所有的 0 都"记下来"，再统一清零。
用第一行、第一列当标记，标记的过程会把第一行、第一列的一些元素改成 0。如果事先没有记下它们原来有没有 0，最后就无法区分"原来就是 0"和"被标记成 0"。下面是省略这一步的写法与 solve 的真实结果：
# 没有单独记录第一行、第一列原来有没有 0 的写法 [[1, 0, 3], [4, 5, 6], [7, 8, 9]]: 该写法 -> [[0, 0, 3], [4, 0, 6], [7, 0, 9]] solve -> [[0, 0, 0], [4, 0, 6], [7, 0, 9]] [[1, 2, 3], [0, 5, 6], [7, 8, 9]]: 该写法 -> [[0, 2, 3], [0, 0, 0], [7, 8, 9]] solve -> [[0, 2, 3], [0, 0, 0], [0, 8, 9]] [[0, 2], [3, 4]]: 该写法 -> [[0, 2], [3, 4]] solve -> [[0, 0], [0, 4]] 随机 20000 个矩阵：该写法与正确答案不同的有 10302 个（51.5%）
[[1, 0, 3], [4, 5, 6], [7, 8, 9]]：第一行原来就有 0，应该整行清零，这种写法只清了那个 0 所在的列，第一行的 1 和 3 没有被清零；[[0, 2], [3, 4]]（0 在左上角，同时属于第一行和第一列）这种写法什么都没有清零。随机的 20000 个矩阵里，这种写法出错的有 10302 个，占 51.5%。
第一步，用两个布尔变量记下第一行、第一列原来有没有 0。第二步，扫描除第一行、第一列以外的所有格子：遇到 0，就把它所在行的标记（第一列的对应位置）和所在列的标记（第一行的对应位置）设为 0。第三步，再扫描除第一行、第一列以外的所有格子：如果所在行标记或所在列标记是 0，这个格子设为 0。最后一步，根据第一步记下的两个布尔变量，决定要不要把第一行、第一列整体清零；这一步必须放在最后，否则会破坏还没读完的标记。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(mat): m, n = len(mat), len(mat[0]) first_row_zero = any(mat[0][j] == 0 for j in range(n)) # 第一行、第一列本身要用来当"标记"，先单独记下它们原来有没有 0 first_col_zero = any(mat[i][0] == 0 for i in range(m)) for i in range(1, m): for j in range(1, n): if mat[i][j] == 0: mat[i][0] = 0 # 用第一列记录"这一行要清零" mat[0][j] = 0 # 用第一行记录"这一列要清零" for i in range(1, m): for j in range(1, n): if mat[i][0] == 0 or mat[0][j] == 0: mat[i][j] = 0 if first_row_zero: # 最后才处理第一行、第一列本身 for j in range(n): mat[0][j] = 0 if first_col_zero: for i in range(m): mat[i][0] = 0 return mat
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[[1,1,1],[1,0,1],[1,1,1]]] → [[1,0,1],[0,0,0],[1,0,1]] [[[0,1,2,0],[3,4,5,2],[1,3,1,5]]] → [[0,0,0,0],[0,4,5,0],[0,3,1,0]] [[[1]]] → [[1]] [[[0]]] → [[0]] [[[1,0]]] → [[0,0]] [[[1],[0]]] → [[0],[0]]
Java · 解法代码class Solution { public void setZeroes(int[][] mat) { int m = mat.length, n = mat[0].length; boolean firstRowZero = false, firstColZero = false; // 第一行、第一列本身要用来当"标记"，先单独记下它们原来有没有 0 for (int j = 0; j < n; j++) if (mat[0][j] == 0) firstRowZero = true; for (int i = 0; i < m; i++) if (mat[i][0] == 0) firstColZero = true; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (mat[i][j] == 0) { mat[i][0] = 0; // 用第一列记录"这一行要清零" mat[0][j] = 0; // 用第一行记录"这一列要清零" } } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (mat[i][0] == 0 || mat[0][j] == 0) mat[i][j] = 0; } } if (firstRowZero) for (int j = 0; j < n; j++) mat[0][j] = 0; // 最后才处理第一行、第一列本身 if (firstColZero) for (int i = 0; i < m; i++) mat[i][0] = 0; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[[1,1,1],[1,0,1],[1,1,1]]] → [[1,0,1],[0,0,0],[1,0,1]] [[[0,1,2,0],[3,4,5,2],[1,3,1,5]]] → [[0,0,0,0],[0,4,5,0],[0,3,1,0]] [[[1]]] → [[1]] [[[0]]] → [[0]] [[[1,0]]] → [[0,0]] [[[1],[0]]] → [[0],[0]]
Go · 解法代码func setZeroes(mat [][]int) { m, n := len(mat), len(mat[0]) firstRowZero, firstColZero := false, false // 第一行、第一列本身要用来当"标记"，先单独记下它们原来有没有 0 for j := 0; j < n; j++ { if mat[0][j] == 0 { firstRowZero = true } } for i := 0; i < m; i++ { if mat[i][0] == 0 { firstColZero = true } } for i := 1; i < m; i++ { for j := 1; j < n; j++ { if mat[i][j] == 0 { mat[i][0] = 0 // 用第一列记录"这一行要清零" mat[0][j] = 0 // 用第一行记录"这一列要清零" } } } for i := 1; i < m; i++ { for j := 1; j < n; j++ { if mat[i][0] == 0 || mat[0][j] == 0 { mat[i][j] = 0 } } } if firstRowZero { // 最后才处理第一行、第一列本身 for j := 0; j < n; j++ { mat[0][j] = 0 } } if firstColZero { for i := 0; i < m; i++ { mat[i][0] = 0 } } }
$ go build -o bin . && ./bin < cases.jsonl [[[1,1,1],[1,0,1],[1,1,1]]] → [[1,0,1],[0,0,0],[1,0,1]] [[[0,1,2,0],[3,4,5,2],[1,3,1,5]]] → [[0,0,0,0],[0,4,5,0],[0,3,1,0]] [[[1]]] → [[1]] [[[0]]] → [[0]] [[[1,0]]] → [[0,0]] [[[1],[0]]] → [[0],[0]]
JavaScript · 解法代码function setZeroes(mat) { const m = mat.length, n = mat[0].length; let firstRowZero = false, firstColZero = false; // 第一行、第一列本身要用来当"标记"，先单独记下它们原来有没有 0 for (let j = 0; j < n; j++) if (mat[0][j] === 0) firstRowZero = true; for (let i = 0; i < m; i++) if (mat[i][0] === 0) firstColZero = true; for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { if (mat[i][j] === 0) { mat[i][0] = 0; // 用第一列记录"这一行要清零" mat[0][j] = 0; // 用第一行记录"这一列要清零" } } } for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { if (mat[i][0] === 0 || mat[0][j] === 0) mat[i][j] = 0; } } if (firstRowZero) for (let j = 0; j < n; j++) mat[0][j] = 0; // 最后才处理第一行、第一列本身 if (firstColZero) for (let i = 0; i < m; i++) mat[i][0] = 0; }
$ node run.js < cases.jsonl [[[1,1,1],[1,0,1],[1,1,1]]] → [[1,0,1],[0,0,0],[1,0,1]] [[[0,1,2,0],[3,4,5,2],[1,3,1,5]]] → [[0,0,0,0],[0,4,5,0],[0,3,1,0]] [[[1]]] → [[1]] [[[0]]] → [[0]] [[[1,0]]] → [[0,0]] [[[1],[0]]] → [[0],[0]]
C++ · 解法代码#include <vector> using namespace std; class Solution { public: void setZeroes(vector<vector<int>>& mat) { int m = mat.size(), n = mat[0].size(); bool firstRowZero = false, firstColZero = false; // 第一行、第一列本身要用来当"标记"，先单独记下它们原来有没有 0 for (int j = 0; j < n; j++) if (mat[0][j] == 0) firstRowZero = true; for (int i = 0; i < m; i++) if (mat[i][0] == 0) firstColZero = true; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (mat[i][j] == 0) { mat[i][0] = 0; // 用第一列记录"这一行要清零" mat[0][j] = 0; // 用第一行记录"这一列要清零" } } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (mat[i][0] == 0 || mat[0][j] == 0) mat[i][j] = 0; } } if (firstRowZero) for (int j = 0; j < n; j++) mat[0][j] = 0; // 最后才处理第一行、第一列本身 if (firstColZero) for (int i = 0; i < m; i++) mat[i][0] = 0; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[[1,1,1],[1,0,1],[1,1,1]]] → [[1,0,1],[0,0,0],[1,0,1]] [[[0,1,2,0],[3,4,5,2],[1,3,1,5]]] → [[0,0,0,0],[0,4,5,0],[0,3,1,0]] [[[1]]] → [[1]] [[[0]]] → [[0]] [[[1,0]]] → [[0,0]] [[[1],[0]]] → [[0],[0]]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
Python 版本另外和"用集合记下含 0 的行、列"的基准做了随机对拍：行数、列数各取 1 到 6，每个格子有 15% 的概率是 0：
随机对拍 20000 组（行数、列数各取 1 到 6，每个格子有 15% 的概率是 0，其余取 1 到 9），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。这道题每个格子只处理常数次，是线性于元素个数的，所以没有做规模对比实验。
下面的演示用 [[1, 2, 0], [4, 5, 6], [7, 0, 9]]：第一行有 0，第一列没有。先记下 first_row_zero = True；扫描内部格子时，在 (2, 1) 发现 0，把它对应的标记 (2, 0) 和 (0, 1) 置为 0；再扫描一遍内部格子，按标记清零；最后因为第一行原来有 0，把整个第一行清零。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。