73. 矩阵置零
4 min
题目
解法：标记法
思路
核心思想是利用矩阵的第一行和第一列作为标记空间，避免额外存储。
正确性证明：通过第一行标记需清零的列，第一列标记需清零的行。先单独记录首行首列原始零状态，再遍历标记非首行首列元素，最后根据标记批量清零。该过程确保每个零的影响被完整记录且不会覆盖原始标记信息。
- Step 1: 检查首行/首列是否存在零并记录
- Step 2: 遍历非首行首列元素，遇零则标记对应行首和列首
- Step 3: 再次遍历非首行首列，根据标记置零元素
- Step 4: 根据初始记录清零首行和首列
复杂度
- 时间复杂度: ，两次完整遍历矩阵，m和n分别为行列数
- 空间复杂度: ，仅使用两个布尔变量和常数个指针
代码
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
bool row0 = false;
bool col0 = false;
//其实为了标记就需要n+m的空间，但是为了压缩我们就可以用第一行和第一列来标记
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
row0 = true;
break;
}
}
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
col0 = true;
break;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
bool row0 = false;
bool col0 = false;
//其实为了标记就需要n+m的空间，但是为了压缩我们就可以用第一行和第一列来标记
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
row0 = true;
break;
}
}
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
col0 = true;
break;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (row0) {
for (int j = 0; j < n; j++) matrix[0][j] = 0;
}
if (col0) {
for (int i = 0; i < m; i++) matrix[i][0] = 0;
}
}
};