Problem: 73. 矩陣置零
題目：給定一個 m x n 的矩陣，如果一個元素為 0 ，則將其所在行和列的所有元素都設為 0 。請使用 原地 算法。

整體思路

這段代碼旨在解決 “矩陣置零” 問題，它通過 HashSet 來存儲需要置零的行和列的索引，并在一個統一的階段完成置零操作。

算法的整體思路是 “先標記，后置零”：

1. 第一階段：使用 HashSet 進行標記

   • 算法創建了兩個哈希集合（HashSet）row 和 col。
   • 優勢：使用 HashSet 而不是 List 有兩個好處：
     a. 自動去重：HashSet 內部保證了元素的唯一性。即使一行或一列有多個 0，其索引也只會被存儲一次，這使得存儲空間更為緊湊。
     b. 高效查找：HashSet 提供了平均時間復雜度為 O(1) 的 contains 操作，這在第二階段的置零操作中會非常高效。
   • 通過一次完整的雙層循環遍歷矩陣，當遇到 matrix[i][j] == 0 時，就將行號 i 和列號 j 分別添加到 row 和 col 集合中。

2. 第二階段：統一置零

   • 它再次遍歷整個矩陣的每一個位置 (i, j)。
   • 對于每個元素 matrix[i][j]，它會檢查：當前元素的行號 i 是否在 row 集合中，或者其列號 j 是否在 col 集合中 (row.contains(i) || col.contains(j))。
   • 如果上述條件滿足，就說明該元素位于一個需要被清零的行或列，因此將其值設置為 0。

完整代碼

class Solution {/*** 將矩陣中包含 0 的元素的整行和整列都置為 0。* @param matrix 一個 M x N 的整數矩陣*/public void setZeroes(int[][] matrix) {// 獲取矩陣的行數和列數int m = matrix.length;int n = matrix[0].length;// 使用 HashSet 來存儲需要置零的行和列的索引，可以自動去重。Set<Integer> row = new HashSet<>();Set<Integer> col = new HashSet<>();// 步驟 1: 遍歷整個矩陣，記錄所有 0 元素所在的行和列索引for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == 0) {// 將行號和列號添加到集合中row.add(i);col.add(j);}}}// 步驟 2: 再次遍歷矩陣，根據集合中的標記進行置零for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 如果當前元素的行號或列號在我們的標記集合中，// 那么這個元素就需要被置為 0。if (row.contains(i) || col.contains(j)) {matrix[i][j] = 0;}}}}
}

時空復雜度

時間復雜度：O(M * N)

1. 標記階段：第一個雙層 for 循環遍歷了矩陣中的每一個元素一次。操作次數為 M * N。HashSet 的 add 操作平均時間復雜度為 O(1)。因此，這部分的總時間復雜度是 O(M * N)。
2. 置零階段：第二個雙層 for 循環也遍歷了矩陣中的每一個元素一次。操作次數為 M * N。
   • 在循環內部，row.contains(i) 和 col.contains(j) 是關鍵操作。由于它們是 HashSet 的操作，其平均時間復雜度為 O(1)。
   • 因此，這部分的總時間復雜度也是 O(M * N)。

綜合分析：
算法的總時間復雜度由兩個獨立的、對矩陣的完整遍歷組成。因此，最終的時間復雜度是 O(M * N) + O(M * N) = O(M * N)。

空間復雜度：O(M + N)

1. 主要存儲開銷：算法創建了兩個 HashSet，row 和 col。
2. 空間大小：
   • row 集合最多存儲 M 個不同的行號（如果每一行都有0）。
   • col 集合最多存儲 N 個不同的列號（如果每一列都有0）。
   • 因此，這兩個集合占用的總空間與 M 和 N 的和成正比。

綜合分析：
算法所需的額外輔助空間主要由 row 和 col 兩個哈希集合決定。因此，其空間復雜度為 O(M + N)。

【LeetCode 熱題 100】73. 矩陣置零——（解法二）空間復雜度 O(1)