leetcode hot100【LeetCode 73.矩阵置零】java实现

LeetCode 73.矩阵置零

题目描述

给定一个 m x n 的矩阵，如果某个元素是 0，则将其所在行和列的所有元素都置为 0。请你实现这个功能，不需要返回矩阵，原地修改矩阵。

示例 1:

输入:

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

输出:

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

示例 2:

输入:

[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]

输出:

[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

Java 实现代码

class Solution {
    public void setZeroes(int[][] matrix) {
        boolean firstRowZero = false;
        boolean firstColZero = false;
        
        // 检查第一行和第一列是否包含零
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }
        
        // 遍历矩阵，标记需要置零的行和列
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        // 根据标记更新矩阵
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // 更新第一行
        if (firstRowZero) {
            for (int j = 0; j < matrix[0].length; j++) {
                matrix[0][j] = 0;
            }
        }
        
        // 更新第一列
        if (firstColZero) {
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

解题思路

1. 检查第一行和第一列：
   • 第一行中有 0，所以 firstRowZero = true。
   • 第一列中有 0，所以 firstColZero = true。
2. 第二步：遍历矩阵，标记需要置零的行和列：
3. 第三步：根据标记更新矩阵：
4. 第四步：更新第一行和第一列：

复杂度分析

• 时间复杂度：O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。我们需要两次遍历整个矩阵。
• 空间复杂度：O(1)，我们只使用了常数空间来标记第一行和第一列。

执行过程示例

输入:

[ [0,1,2,0], [3,4,5,2], [1,3,1,5] ]

1. 第一步：检查第一行和第一列：

   • 第一行中有 0，所以 firstRowZero = true。
   • 第一列中有 0，所以 firstColZero = true。

2. 第二步：遍历矩阵，标记需要置零的行和列：

   • matrix[1][1] = 4，matrix[1][2] = 5，都不是零，不做标记。
   • matrix[2][1] = 3，matrix[2][2] = 1，都不是零，不做标记。

   在矩阵的标记阶段，matrix[i][0] 和 matrix[0][j] 被更新为零，以便后续操作。

3. 第三步：根据标记更新矩阵：

   • 第二行第二列及之后的元素根据标记被置零。

4. 第四步：更新第一行和第一列：

   • 第一行和第一列的所有元素被置为零。

最终结果：

[ [0,0,0,0], [0,4,5,0], [0,3,1,0] ]