73. 矩陣置零 - 力扣（LeetCode）

暴力解法

用兩個標記數組分別記錄每一行和每一列是否有零出現。

• 遍歷該數組一次，如果某個元素為 0，那么就將該元素所在的行和列所對應標記數組的位置置為 true。
• 再次遍歷該數組，用標記數組更新原數組即可。

時間復雜度：O(mn)，其中 m 是矩陣的行數，n?是矩陣的列數。至多只需要遍歷該矩陣兩次。

空間復雜度：O(m+n)，其中 m?是矩陣的行數，n 是矩陣的列數。需要分別記錄每一行或每一列是否有零出現。

public class Solution {public void SetZeroes(int[][] matrix) {int m = matrix.Length, n = matrix[0].Length;bool[] row = new bool[m];bool[] col = new bool[n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == 0) {row[i] = 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;}}}}
}

使用兩個標記變量

使用兩個額外的變量記錄原矩陣的第一行第一列是否包含0。之后便可以修改matrix[0][j]和 matrix[i][0]的數據。

用原矩陣的 第一行 matrix[0][j] 和第一列 matrix[i][0]，來代替原來的兩個標記數組，從而減少使用的空間。

public class Solution {public void SetZeroes(int[][] matrix) {int m = matrix.Length, n = matrix[0].Length;bool flagCol0 = false, flagRow0 = false;//第一列for(int i = 0; i < m; i++){if(matrix[i][0] == 0){flagCol0 = true;break;}}//第一行for(int j = 0; j < n; j++){if(matrix[0][j] == 0){flagRow0 = true;break;}}//從第二行第二列開始遍歷矩陣,將0結點的行列保存在第一行第一列中for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){if(matrix[i][j] == 0)matrix[i][0] = matrix[0][j] = 0;}}//從第二行第二列開始遍歷矩陣,根據第一行第一列中的的0修改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;}}//修改第一列if(flagCol0){for(int i = 0; i < m; i++)matrix[i][0] = 0;}//修改第一行if(flagRow0){for(int j = 0; j < n; j++)matrix[0][j] = 0;}}
}

時間復雜度：O(mn)，其中 m 是矩陣的行數，n 是矩陣的列數。我們至多只需要遍歷該矩陣兩次。

空間復雜度：O(1)。我們只需要常數空間存儲若干變量。