73. 矩阵置零

题目：矩阵置零

描述

给定一个 m x n 的矩阵，如果其中一个元素为 0，则将其所在行和列的所有元素都设置为 0。要求使用 原地算法，即在不使用额外空间的情况下完成操作。

---

示例

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

---

解题思路

常规解法

通常解法需要一个额外的矩阵或集合记录所有为 0 的位置，但这不符合题目要求的 原地算法。

原地算法

为了在原地完成操作，我们可以用矩阵的第一行和第一列来标记哪些行和列需要被置为 0。

思路：

1. 标记需要置零的行和列：
   • 遍历矩阵，当发现某个元素为 0 时：
     • 将对应行的第一个元素置为 0（标记该行需要置零）。
     • 将对应列的第一个元素置为 0（标记该列需要置零）。
2. 根据标记置零：
   • 再次遍历矩阵（从第二行和第二列开始，避免覆盖标记信息）。
   • 根据第一行和第一列的标记，将对应的元素置为 0。
3. 处理第一行和第一列：
   • 根据标记信息，最后处理第一行和第一列，完成置零。

---

代码实现

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read matrix dimensions
        int m = scanner.nextInt();
        int n = scanner.nextInt();

        // Read matrix elements
        int[][] matrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }

        Solution solution = new Solution();
        solution.setZeroes(matrix);

        // Print the modified matrix
        for (int i = 0; i < m; i++) {
            System.out.println(Arrays.toString(matrix[i]));
        }

        scanner.close();
    }
}

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        // 标记第一行和第一列是否需要置零
        boolean firstRowZero = false;
        boolean firstColZero = false;

        // Step 1: 遍历矩阵，标记需要置零的行和列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    if (i == 0) firstRowZero = true; // 标记第一行
                    if (j == 0) firstColZero = true; // 标记第一列
                    matrix[i][0] = 0; // 标记所在行
                    matrix[0][j] = 0; // 标记所在列
                }
            }
        }

        // Step 2: 根据标记置零（跳过第一行和第一列）
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Step 3: 处理第一行
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }

        // Step 4: 处理第一列
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

---

代码解析

示例：matrix = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]

1. 初始标记：

   • 第一行和第一列是否需要置零：

     • 第一行需要置零，因为 matrix[0][0] 和 matrix[0][3] 为 0。
     • 第一列需要置零，因为 matrix[0][0] 为 0。

   • 标记其他行和列：

     • 标记第 1 行：matrix[1][0] = 0。
     • 标记第 0 列：matrix[0][1] = 0，matrix[0][3] = 0。

   • 矩阵状态：

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

2. 根据标记置零：

   • 遍历矩阵，从第 2 行和第 2 列开始：
     • 第 1 行第 1 列：matrix[1][1] = 0（因为 matrix[0][1] = 0）。
     • 依次处理，结果：

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

3. 处理第一行和第一列：

   • 第一行置零：

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

   • 第一列置零：

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

---

时间复杂度

1. 遍历矩阵：
   • 遍历两次矩阵，时间复杂度为 O(m * n)。

总时间复杂度：O(m * n)。

---

空间复杂度

1. 不使用额外数组，只用常数变量记录第一行和第一列的标记信息。

总空间复杂度：O(1)。

---

总结

• 为什么标记第一行和第一列？

  • 这是为了避免额外空间的使用，同时可以利用矩阵本身存储标记信息。

• 为什么先标记再置零？

  • 如果直接修改，会影响后续标记过程。先记录需要置零的行列，后续统一处理更安全。

• 优势：高效，符合题目对时间和空间的要求。