這是一道難度為中等的題目，讓我們來看看題目描述：

給定一個 _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。
• 這樣就符合題目的要求，用 兩次遍歷 實現 原地置零。