73. 矩阵置零
一句话套路借第一行第一列当标记位,O(1) 空间
题目描述
给定一个 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(mn)空间
O(1)思路
用第 0 行 / 第 0 列作为「这一行/列要不要清零」的标记数组。
先单独记录第 0 行、第 0 列本身是否含 0,最后再处理它们。
顺序不能反
标记位写在最后处理,否则会被自己新写的 0 污染。
图解
矩阵(来自本仓库测试数据,红色格子 = 0)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0073 {
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return; // 题面保证 m,n ≥ 1,本地防越界
const int R = (int)matrix.size(), C = (int)matrix[0].size();
bool zeroRow = false, zeroCol = false;
for (int j = 0; j < C; ++j)
if (matrix[0][j] == 0) zeroRow = true;
for (int i = 0; i < R; ++i)
if (matrix[i][0] == 0) zeroCol = true;
for (int i = 1; i < R; ++i)
for (int j = 1; j < C; ++j)
if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0; // 打标记
for (int i = 1; i < R; ++i)
for (int j = 1; j < C; ++j)
if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
if (zeroRow)
for (int j = 0; j < C; ++j) matrix[0][j] = 0;
if (zeroCol)
for (int i = 0; i < R; ++i) matrix[i][0] = 0;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0073::Solution s;
vector<vector<int>> a{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
s.setZeroes(a);
CHECK_EQ(a, vector<vector<int>>({{1, 0, 1}, {0, 0, 0}, {1, 0, 1}}));
vector<vector<int>> b{{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
s.setZeroes(b);
CHECK_EQ(b, vector<vector<int>>({{0, 0, 0, 0}, {0, 4, 5, 0}, {0, 3, 1, 0}}));
vector<vector<int>> c{{1}};
s.setZeroes(c);
CHECK_EQ(c, vector<vector<int>>({{1}}));