【LeetCode 热题 100】73. 矩阵置零——(解法一)空间复杂度 O(M + N)

发布于:2025-07-07 ⋅ 阅读:(13) ⋅ 点赞:(0)

Problem: 73. 矩阵置零
题目:给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

整体思路

这段代码旨在解决 “矩阵置零” 问题,它通过 HashSet 来存储需要置零的行和列的索引,并在一个统一的阶段完成置零操作。

算法的整体思路是 “先标记,后置零”

  1. 第一阶段:使用 HashSet 进行标记

    • 算法创建了两个哈希集合(HashSetrowcol
    • 优势:使用 HashSet 而不是 List 有两个好处:
      a. 自动去重HashSet 内部保证了元素的唯一性。即使一行或一列有多个 0,其索引也只会被存储一次,这使得存储空间更为紧凑。
      b. 高效查找HashSet 提供了平均时间复杂度为 O(1) 的 contains 操作,这在第二阶段的置零操作中会非常高效。
    • 通过一次完整的双层循环遍历矩阵,当遇到 matrix[i][j] == 0 时,就将行号 i 和列号 j 分别添加到 rowcol 集合中。
  2. 第二阶段:统一置零

    • 它再次遍历整个矩阵的每一个位置 (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)

  1. 标记阶段:第一个双层 for 循环遍历了矩阵中的每一个元素一次。操作次数为 M * NHashSetadd 操作平均时间复杂度为 O(1)。因此,这部分的总时间复杂度是 O(M * N)
  2. 置零阶段:第二个双层 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)
  1. 主要存储开销:算法创建了两个 HashSetrowcol
  2. 空间大小
    • row 集合最多存储 M 个不同的行号(如果每一行都有0)。
    • col 集合最多存储 N 个不同的列号(如果每一列都有0)。
    • 因此,这两个集合占用的总空间与 MN 的和成正比。

综合分析
算法所需的额外辅助空间主要由 rowcol 两个哈希集合决定。因此,其空间复杂度为 O(M + N)

【LeetCode 热题 100】73. 矩阵置零——(解法二)空间复杂度 O(1)


网站公告

今日签到

点亮在社区的每一天
去签到