企业网站备案在哪个部门,门户网站开发项目的风险,c 网站开发连接mysql,西安网站建设加q47918570073. 矩阵置零 - 力扣#xff08;LeetCode#xff09;
暴力解法
用两个标记数组分别记录每一行和每一列是否有零出现。
遍历该数组一次#xff0c;如果某个元素为 0#xff0c;那么就将该元素所在的行和列所对应标记数组的位置置为 true。再次遍历该数组#xff0c;用标…73. 矩阵置零 - 力扣LeetCode
暴力解法
用两个标记数组分别记录每一行和每一列是否有零出现。
遍历该数组一次如果某个元素为 0那么就将该元素所在的行和列所对应标记数组的位置置为 true。再次遍历该数组用标记数组更新原数组即可。
时间复杂度O(mn)其中 m 是矩阵的行数n 是矩阵的列数。至多只需要遍历该矩阵两次。
空间复杂度O(mn)其中 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)。我们只需要常数空间存储若干变量。
