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

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

整体思路

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

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

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

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

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 * N。HashSet 的 add 操作平均时间复杂度为 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. 主要存储开销：算法创建了两个 HashSet，row 和 col。
2. 空间大小：
   • row 集合最多存储 M 个不同的行号（如果每一行都有0）。
   • col 集合最多存储 N 个不同的列号（如果每一列都有0）。
   • 因此，这两个集合占用的总空间与 M 和 N 的和成正比。

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

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