題目
#

leetcode 73 - Set Matrix Zeroes (題目說明請點連結)

題目簡述
#

給一個 m×n 的矩陣，如果一個元素為 0，則將其所在的行和列的所有元素都設為 0。
要求：必須在原地操作，不能使用額外的矩陣空間。

範例
#

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

原始矩陣：
┌───┬───┬───┐
│ 1 │ 1 │ 1 │
├───┼───┼───┤
│ 1 │ 0 │ 1 │  ← 發現 0 元素在位置 (1,1)
├───┼───┼───┤
│ 1 │ 1 │ 1 │
└───┴───┴───┘

最終結果：
┌───┬───┬───┐
│ 1 │ 0 │ 1 │  ← 第 1 列置零
├───┼───┼───┤
│ 0 │ 0 │ 0 │  ← 第 1 行置零
├───┼───┼───┤
│ 1 │ 0 │ 1 │  ← 第 1 列置零
└───┴───┴───┘

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

原始矩陣：
┌───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 0 │  ← 發現 0 元素在位置 (0,0) 和 (0,3)
├───┼───┼───┼───┤
│ 3 │ 4 │ 5 │ 2 │
├───┼───┼───┼───┤
│ 1 │ 3 │ 1 │ 5 │
└───┴───┴───┴───┘

最終結果：
┌───┬───┬───┬───┐
│ 0 │ 0 │ 0 │ 0 │  ← 第 0 行和第 0 列置零
├───┼───┼───┼───┤
│ 0 │ 4 │ 5 │ 0 │  ← 第 0 列和第 3 列置零
├───┼───┼───┼───┤
│ 0 │ 3 │ 1 │ 0 │  ← 第 0 列和第 3 列置零
└───┴───┴───┴───┘

解題思路
#

這題要求我們將矩陣中所有 0 元素所在的行和列都設為 0。我們可以使用兩個 HashSet 來記錄需要設為 0 的行和列，然後遍歷矩陣進行置零操作。

解法
#

創建兩個 HashSet：zeroRow 和 zeroCol，分別記錄需要設為 0 的行和列
遍歷矩陣，找到所有 0 元素，將其行號和列號加入對應的 HashSet
遍歷 zeroRow，將對應行的所有元素設為 0
遍歷 zeroCol，將對應列的所有元素設為 0

步驟
#

初始化 HashSet：
- 創建 Set<Integer> zeroRow 記錄需要設為 0 的行
- 創建 Set<Integer> zeroCol 記錄需要設為 0 的列
記錄 0 元素位置：
- 遍歷矩陣，如果 matrix[i][j] == 0
- 將 i 加入 zeroRow，將 j 加入 zeroCol
置零操作：
- 遍歷 zeroRow，將對應行的所有元素設為 0
- 遍歷 zeroCol，將對應列的所有元素設為 0

例子說明
#

matrix = [[1,1,1],[1,0,1],[1,1,1]]

步驟	操作	矩陣狀態	說明
初始化	-	`[[1,1,1],[1,0,1],[1,1,1]]`	創建 `zeroRow = {}`, `zeroCol = {}`
找到 0 元素	發現 `matrix[1][1] = 0`	`[[1,1,1],[1,0,1],[1,1,1]]`	`zeroRow = {1}`, `zeroCol = {1}`
行置零	將第 1 行設為 0	`[[1,1,1],[0,0,0],[1,1,1]]`	遍歷 `zeroRow = {1}`
列置零	將第 1 列設為 0	`[[1,0,1],[0,0,0],[1,0,1]]`	遍歷 `zeroCol = {1}`

最終結果： [[1,0,1],[0,0,0],[1,0,1]]

步驟 1: 原始矩陣

┌───┬───┬───┐
│ 1 │ 1 │ 1 │
├───┼───┼───┤
│ 1 │ 0 │ 1 │  ← 發現 0 元素在位置 (1,1)
├───┼───┼───┤
│ 1 │ 1 │ 1 │
└───┴───┴───┘

步驟 2: 行置零（將第 1 行設為 0）

┌───┬───┬───┐
│ 1 │ 1 │ 1 │
├───┼───┼───┤
│ 0 │ 0 │ 0 │  ← 第 1 行全部設為 0
├───┼───┼───┤
│ 1 │ 1 │ 1 │
└───┴───┴───┘

步驟 3: 列置零（將第 1 列設為 0）

┌───┬───┬───┐
│ 1 │ 0 │ 1 │  ← 第 1 列全部設為 0
├───┼───┼───┤
│ 0 │ 0 │ 0 │
├───┼───┼───┤
│ 1 │ 0 │ 1 │  ← 第 1 列全部設為 0
└───┴───┴───┘

矩陣置零過程說明：

步驟 1: 原始 3×3 矩陣，其中 matrix[1][1] = 0
步驟 2: 將第 1 行（索引從 0 開始）的所有元素設為 0
步驟 3: 將第 1 列的所有元素設為 0，得到最終結果

完整程式碼
#

java

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

        // 創建兩個 HashSet 記錄需要設為 0 的行和列
        Set<Integer> zeroCol = new HashSet<>();
        Set<Integer> zeroRow = new HashSet<>();

        // 遍歷矩陣，找到所有 0 元素
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    zeroCol.add(j);
                    zeroRow.add(i);
                }
            }
        }

        // 將需要設為 0 的行全部設為 0
        for (int row : zeroRow) {
            for (int j = 0; j < n; j++) {
                matrix[row][j] = 0;
            }
        }

        // 將需要設為 0 的列全部設為 0
        for (int col : zeroCol) {
            for (int i = 0; i < m; i++) {
                matrix[i][col] = 0;
            }
        }
    }
}