LeetCode hot 100 每日一题(13)——73. 矩阵置零

这是一道难度为中等的题目，让我们来看看题目描述：

给定一个 _m_ x _n_ 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -$2^{31}$ <= matrix[i][j] <= $2^{31}$ - 1

题解

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;  // 获取矩阵的行数
        int n = matrix[0].length; // 获取矩阵的列数

        boolean[] row = new boolean[m]; // 记录需要置零的行
        boolean[] col = new boolean[n]; // 记录需要置零的列
        
        // 第一遍遍历矩阵，标记所有含有 0 的行和列
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 0){ 
                    row[i] = true;  // 标记该行需要置零
                    col[j] = true;  // 标记该列需要置零
                }
            }
        }

        // 第二遍遍历矩阵，根据标记的行和列将相应元素置零
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(row[i] || col[j]){ // 如果当前行或列被标记为需要置零
                    matrix[i][j] = 0; // 置零操作
                }
            }
        }
    }
}

解题思路

1. 题目分析

给定一个 m × n 的矩阵，如果某个元素为 0，则需要将它所在的整行和整列的所有元素都设为 0。要求在原矩阵上直接修改，不能使用额外的矩阵存储修改后的数据。

2. 解法思路

• 第一步：标记所有需要置零的行和列

  • 用两个数组 row[] 和 col[] 分别记录哪些行和列需要置零。

  • 遍历矩阵，如果遇到 matrix[i][j] == 0，就将 row[i] 和 col[j] 标记为 true，表示该行或该列需要全部置零。

• 第二步：遍历矩阵，根据标记进行置零

  • 再次遍历矩阵，如果 row[i] 为 true 或 col[j] 为 true，说明该位置 matrix[i][j] 需要置零。

3. 复杂度分析

• 时间复杂度：O(m × n)

  • 需要两次遍历整个矩阵，时间复杂度为 O(m × n)，符合题目要求。

• 空间复杂度：O(m + n)

  • 额外使用了 row[] 和 col[] 两个数组，空间复杂度为 O(m + n)。

4. 进阶优化

如果希望减少额外空间使用，可以利用矩阵的第一行和第一列来存储这些标记，而不使用额外的 row[] 和 col[] 数组，进而将空间复杂度优化为 O(1)。

问题与解答

[NOTE] 问题1：
if(row[i] || col[j])这一句我有一点不懂，为什么要么行或列被标记，就会被置0呢？
解答：
这个 if(row[i] || col[j]) 条件的作用是：如果当前元素所在的行 i 或列 j 需要置零，则将该元素 matrix[i][j] 置为 0。

---

为什么这样判断？

想象一下矩阵的置零规则：

• 如果一个元素 matrix[i][j] == 0，那么它所在的整行 和 整列 都要变成 0。
• 在第一遍遍历矩阵时，我们用 row[i] 记录第 i 行是否需要全部变 0，用 col[j] 记录第 j 列是否需要全部变 0。
• 因此，在第二遍遍历时：
  • 如果 row[i] == true，说明该行有一个元素原本是 0，所以整行要变 0，当前元素 matrix[i][j] 也必须变 0。
  • 如果 col[j] == true，说明该列有一个元素原本是 0，所以整列要变 0，当前元素 matrix[i][j] 也必须变 0。
  • 只要满足任意一个条件 (row[i] 或 col[j])，当前元素 matrix[i][j] 必须变成 0。

---

举例分析

示例 1

输入矩阵：

[
   [1, 1, 1],
  [1, 0, 1],
   [1, 1, 1]
]

第一遍标记 row[] 和 col[]

row = [false, true, false]  // 第 1 行（索引 1）需要置零
col = [false, true, false]  // 第 1 列（索引 1）需要置零

第二遍遍历并置零（应用 if(row[i] || col[j])）

[
  [1, 0, 1],  // 因为 col[1] = true，第二列所有元素变 0
   [0, 0, 0],  // 因为 row[1] = true，整行变 0
   [1, 0, 1]   // 因为 col[1] = true，第二列所有元素变 0
]

总结

• row[i] 记录行是否要变 0，col[j] 记录列是否要变 0。
• if(row[i] || col[j]) 的含义是：
  • 如果这一行之前有 0，则当前行的所有元素都要变 0。
  • 如果这一列之前有 0，则当前列的所有元素都要变 0。
  • 如果当前行或列任意一个需要变 0，那么 matrix[i][j] 也必须变 0。
• 这样就符合题目的要求，用 两次遍历 实现 原地置零。