0073. 矩阵置零
https://leetcode-cn.com/problems/set-matrix-zeroes/
给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例 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]
]
进阶:
一个直接的解决方案是使用 O(mn) 的额外空间,但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗?
- 状态压缩
- 阿里
- 百度
- 字节
符合直觉的想法是,使用一个 m + n 的数组来表示每一行每一列是否”全部是 0“, 先遍历一遍去构建这样的 m + n 数组,然后根据这个 m + n 数组去修改 matrix 即可。

73.set-matrix-zeroes-1
这样的时间复杂度 O(m * n), 空间复杂度 O(m + n).
代码如下:
var setZeroes = function (matrix) {
if (matrix.length === 0) return matrix;
const m = matrix.length;
const n = matrix[0].length;
const zeroes = Array(m + n).fill(false);
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
const item = matrix[i][j];
if (item === 0) {
zeroes[i] = true;
zeroes[m + j] = true;
}
}
}
for (let i = 0; i < m; i++) {
if (zeroes[i]) {
matrix[i] = Array(n).fill(0);
}
}
for (let i = 0; i < n; i++) {
if (zeroes[m + i]) {
for (let j = 0; j < m; j++) {
matrix[j][i] = 0;
}
}
}
return matrix;
};
但是这道题目还有一个 follow up, 要求使用 O(1)的时间复杂度。因此上述的方法就不行了。 但是我们要怎么去存取这些信息(哪一行哪一列应该全部为 0)呢?
一种思路是使用第一行第一列的数据来代替上述的 zeros 数组。 这样我们就不必借助额外的存储空间,空间复杂度自然就是 O(1)了。
由于我们不能先操作第一行和第一列, 因此我们需要记录下”第一行和第一列是否全是 0“这样的一个数据,最后根据这个信息去 修改第一行和第一列。
具体步骤如下:
- 记录下”第一行和第一列是否全是 0“这样的一个数据
- 遍历除了第一行和第一列之外的所有的数据,如果是 0,那就更新第一行第一列中对应的元素为 0你可以把第一行第一列看成我们上面那种解法使用的 m + n 数组。
- 根据第一行第一列的数据,更新 matrix
- 最后根据我们最开始记录的”第一行和第一列是否全是 0“去更新第一行和第一列即可

73.set-matrix-zeroes-2
- 使用第一行和第一列来替代我们 m + n 数组
- 先记录下”第一行和第一列是否全是 0“这样的一个数据,否则会因为后续对第一行第一列的更新造成数据丢失
- 最后更新第一行第一列
- 语言支持:JS,Python3
/*
* @lc app=leetcode id=73 lang=javascript
*
* [73] Set Matrix Zeroes
*/
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function (matrix) {
if (matrix.length === 0) return matrix;
const m = matrix.length;
const n = matrix[0].length;