Problem: 73. 矩阵置零
题目:给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
整体思路
这段代码旨在解决 “矩阵置零” 问题,它通过 HashSet
来存储需要置零的行和列的索引,并在一个统一的阶段完成置零操作。
算法的整体思路是 “先标记,后置零”:
第一阶段:使用
HashSet
进行标记- 算法创建了两个哈希集合(
HashSet
)row
和col
。 - 优势:使用
HashSet
而不是List
有两个好处:
a. 自动去重:HashSet
内部保证了元素的唯一性。即使一行或一列有多个 0,其索引也只会被存储一次,这使得存储空间更为紧凑。
b. 高效查找:HashSet
提供了平均时间复杂度为 O(1) 的contains
操作,这在第二阶段的置零操作中会非常高效。 - 通过一次完整的双层循环遍历矩阵,当遇到
matrix[i][j] == 0
时,就将行号i
和列号j
分别添加到row
和col
集合中。
- 算法创建了两个哈希集合(
第二阶段:统一置零
- 它再次遍历整个矩阵的每一个位置
(i, j)
。 - 对于每个元素
matrix[i][j]
,它会检查:当前元素的行号i
是否在row
集合中,或者其列号j
是否在col
集合中 (row.contains(i) || col.contains(j)
)。 - 如果上述条件满足,就说明该元素位于一个需要被清零的行或列,因此将其值设置为 0。
- 它再次遍历整个矩阵的每一个位置
完整代码
class Solution {
/**
* 将矩阵中包含 0 的元素的整行和整列都置为 0。
* @param matrix 一个 M x N 的整数矩阵
*/
public void setZeroes(int[][] matrix) {
// 获取矩阵的行数和列数
int m = matrix.length;
int n = matrix[0].length;
// 使用 HashSet 来存储需要置零的行和列的索引,可以自动去重。
Set<Integer> row = new HashSet<>();
Set<Integer> col = new HashSet<>();
// 步骤 1: 遍历整个矩阵,记录所有 0 元素所在的行和列索引
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
// 将行号和列号添加到集合中
row.add(i);
col.add(j);
}
}
}
// 步骤 2: 再次遍历矩阵,根据集合中的标记进行置零
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 如果当前元素的行号或列号在我们的标记集合中,
// 那么这个元素就需要被置为 0。
if (row.contains(i) || col.contains(j)) {
matrix[i][j] = 0;
}
}
}
}
}
时空复杂度
时间复杂度:O(M * N)
- 标记阶段:第一个双层
for
循环遍历了矩阵中的每一个元素一次。操作次数为M * N
。HashSet
的add
操作平均时间复杂度为 O(1)。因此,这部分的总时间复杂度是 O(M * N)。 - 置零阶段:第二个双层
for
循环也遍历了矩阵中的每一个元素一次。操作次数为M * N
。- 在循环内部,
row.contains(i)
和col.contains(j)
是关键操作。由于它们是HashSet
的操作,其平均时间复杂度为 O(1)。 - 因此,这部分的总时间复杂度也是 O(M * N)。
- 在循环内部,
综合分析:
算法的总时间复杂度由两个独立的、对矩阵的完整遍历组成。因此,最终的时间复杂度是 O(M * N) + O(M * N) = O(M * N)。
空间复杂度:O(M + N)
- 主要存储开销:算法创建了两个
HashSet
,row
和col
。 - 空间大小:
row
集合最多存储M
个不同的行号(如果每一行都有0)。col
集合最多存储N
个不同的列号(如果每一列都有0)。- 因此,这两个集合占用的总空间与
M
和N
的和成正比。
综合分析:
算法所需的额外辅助空间主要由 row
和 col
两个哈希集合决定。因此,其空间复杂度为 O(M + N)。