当前位置：首页 > web >正文

【Hot100】 73. 矩阵置零

web 2025/7/18 0:04:26

引言

矩阵置零

🎈 题目链接：https://leetcode.cn/problems/set-matrix-zeroes/description/?envType=study-plan-v2&envId=top-100-liked
🎈 做题状态：

我的解题

我的思路还是很明确的，代码写出来也很容易看懂，然后就是分析一下复杂度：

时间复杂度：O(m*n)
空间复杂度：O(m*n) 根据矩阵中0的个数来决定。

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {// 使用两个哈希表来存储行、列为0的索引，使用unordered_set刚好可以去重unordered_set<int> row; // 行unordered_set<int> col; // 列for (int i = 0; i < matrix.size(); ++i){for (int j = 0; j < matrix[0].size(); ++j){if (matrix[i][j] == 0){row.insert(i);col.insert(j);}}}for (int i = 0; i < matrix.size(); ++i){for (int j = 0; j < matrix[0].size(); ++j){if ( row.find(i) != row.end() || col.find(j) != col.end() ){matrix[i][j] = 0;}}}}
};

优化

将矩阵中某个元素为0时，其所在的行和列全部置零。要求空间复杂度为 O(1)（即原地修改）。

优化思路

问题分析：
- 直接遍历矩阵并记录需要置零的行列，需要额外的空间存储标记（如哈希表），空间复杂度为 O(m+n)。
- 优化方向：利用矩阵自身的首行和首列作为标记位，避免额外空间。
关键挑战：
- 首行和首列本身可能包含0，直接使用它们作为标记位时，需要确保这些原始0的标记不被覆盖。

分步解决思路

步骤1：预先检查首行和首列是否有0

目的：记录首行和首列的原始状态，避免后续标记覆盖这些信息。
操作：
- 遍历第一行，检查是否有0 → 记录到 firstRowZero。
- 遍历第一列，检查是否有0 → 记录到 firstColZero。

步骤2：标记需要置零的行和列

范围：从第二行第二列开始（即非首行、非首列）。
规则：如果 matrix[i][j] == 0，则：
- 标记行：将该行首元素置零 → matrix[i][0] = 0。
- 标记列：将该列首元素置零 → matrix[0][j] = 0。
意义：利用首行和首列作为“开关”，标记哪些行和列需要置零。

步骤3：根据标记置零其他元素

范围：从第二行第二列开始。
规则：如果某行的首元素为0（matrix[i][0] == 0）或某列的首元素为0（matrix[0][j] == 0），则将该元素置零。

步骤4：最后处理首行和首列

首行置零：如果 firstRowZero 为 true，将整个第一行置零。
首列置零：如果 firstColZero 为 true，将整个第一列置零。

为什么必须按照这个顺序处理？

1. 预先检查首行首列

问题：如果首行或首列原本有0，后续标记时会覆盖它们的值，导致无法判断是否需要最终置零。
解决：先记录首行首列的原始状态（是否有0），后续标记不会影响这一信息。

2. 最后处理首行首列

问题：如果提前处理首行首列（如先置零），会导致标记位被覆盖。
示例：
- 原始矩阵：
```
0 2 3
4 5 6
```
- 错误做法：
  1. 先处理首行 → 置零首行。
  2. 后续标记其他行列时，首行已被清零，无法正确标记。
- 正确做法：
  1. 先标记其他行列 → 首行保持原样。
  2. 最后根据 firstRowZero 置零首行。

完整示例演示

原始矩阵：

步骤1：检查首行首列

首行无0 → firstRowZero = false。
首列有0（第4行） → firstColZero = true。

步骤2：标记其他行列

发现 matrix[1][1] = 0（第2行第2列）：
- 标记行 → matrix[1][0] = 0。
- 标记列 → matrix[0][1] = 0。

标记后的首行首列：

1 0 3 4  ← 首行第2列被标记为0
0 ...    ← 第2行首列被标记为0

步骤3：根据标记置零

所有行首或列首为0的位置：
- 第2行 → 整行置零。
- 第2列 → 整列置零。
结果：
```
1 0 3 4
0 0 0 0
9 0 11 12
0 0 15 16
```

步骤4：处理首列

因为 firstColZero = true，将首列置零：
```
0 0 3 4
0 0 0 0
0 0 11 12
0 0 15 16
```

总结

核心思想：利用首行首列作为标记位，避免额外空间。
关键顺序：
- 先记录首行首列的原始状态。
- 再标记其他行列。
- 最后处理首行首列。
避免覆盖标记：首行首列的原始0必须在标记完成后处理，否则标记会被破坏。

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {// 检查矩阵是否为空if (matrix.empty()) return;int m = matrix.size();     // 行数int n = matrix[0].size();  // 列数// 标记第一行和第一列是否需要置零（因为它们会被用来记录其他行列的状态，需要最后处理）bool firstRowZero = false; // 第一行是否需要置零bool firstColZero = false; // 第一列是否需要置零// 检查第一行是否有0（注意：单独处理，避免后续覆盖标记）for (int j = 0; j < n; ++j) {if (matrix[0][j] == 0) {firstRowZero = true;break; // 发现0即可退出循环}}// 检查第一列是否有0for (int i = 0; i < m; ++i) {if (matrix[i][0] == 0) {firstColZero = true;break;}}// -------------------- 核心步骤 --------------------// 从第二行第二列开始遍历，用第一行和第一列记录需要置零的行列for (int i = 1; i < m; ++i) {for (int j = 1; j < n; ++j) {if (matrix[i][j] == 0) {// 将当前行的首元素标记为0（表示这一行需要置零）matrix[i][0] = 0;// 将当前列的首元素标记为0（表示这一列需要置零）matrix[0][j] = 0;}}}// 根据第一行和第一列的标记，将对应的元素置零for (int i = 1; i < m; ++i) {for (int j = 1; j < n; ++j) {// 如果当前行或列的首元素是0，说明这个位置需要置零if (matrix[i][0] == 0 || matrix[0][j] == 0) {matrix[i][j] = 0;}}}// -------------------- 核心步骤结束 --------------------// 处理第一行是否需要置零if (firstRowZero) {for (int j = 0; j < n; ++j) {matrix[0][j] = 0;}}// 处理第一列是否需要置零if (firstColZero) {for (int i = 0; i < m; ++i) {matrix[i][0] = 0;}}}
};