别人公司网站进不去,竞争对手网站分析,wordpress模板在哪个目录,广州网站建设费用优质博文#xff1a;IT-BLOG-CN
一、题目
给定一个m x n的矩阵#xff0c;如果一个元素为0#xff0c;则将其所在行和列的所有元素都设为0。请使用原地算法。
示例 1#xff1a; 输入#xff1a;matrix [[1,1,1],[1,0,1],[1,1,1]] 输出#xff1a;[[1,0,1],[0,0,0],[…优质博文IT-BLOG-CN
一、题目
给定一个m x n的矩阵如果一个元素为0则将其所在行和列的所有元素都设为0。请使用原地算法。
示例 1 输入matrix [[1,1,1],[1,0,1],[1,1,1]] 输出[[1,0,1],[0,0,0],[1,0,1]]
示例 2 输入matrix [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出[[0,0,0,0],[0,4,5,0],[0,3,1,0]] m matrix.length n matrix[0].length 1 m, n 200 -231 matrix[i][j] 231 - 1 二、代码
【1】使用标记数组 我们可以用两个标记数组分别记录每一行和每一列是否有零出现。具体地我们首先遍历该数组一次如果某个元素为0那么就将该元素所在的行和列所对应标记数组的位置置为true。最后我们再次遍历该数组用标记数组更新原数组即可。
class Solution {public void setZeroes(int[][] matrix) {int m matrix.length, n matrix[0].length;boolean[] row new boolean[m];boolean[] col new boolean[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;}}}}
}时间复杂度 O(mn)其中m是矩阵的行数n是矩阵的列数。我们至多只需要遍历该矩阵两次。 空间复杂度 O(mn)其中m是矩阵的行数n是矩阵的列数。我们需要分别记录每一行或每一列是否有零出现。
【2】使用两个标记变量 我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组以达到O(1)的额外空间。但这样会导致原数组的第一行和第一列被修改无法记录它们是否原本包含 000。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含0。在实际代码中我们首先预处理出两个标记变量接着使用其他行与列去处理第一行与第一列然后反过来使用第一行与第一列去更新其他行与列最后使用两个标记变量更新第一行与第一列即可。
class Solution {public void setZeroes(int[][] matrix) {int m matrix.length, n matrix[0].length;boolean flagCol0 false, flagRow0 false;for (int i 0; i m; i) {if (matrix[i][0] 0) {flagCol0 true;}}for (int j 0; j n; j) {if (matrix[0][j] 0) {flagRow0 true;}}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;}}}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)。我们只需要常数空间存储若干变量。
使用一个标记变量 我们可以对方法二进一步优化只使用一个标记变量记录第一列是否原本存在0。这样第一列的第一个元素即可以标记第一行是否出现0。但为了防止每一列的第一个元素被提前更新我们需要从最后一行开始倒序地处理矩阵元素。
class Solution {public void setZeroes(int[][] matrix) {int m matrix.length, n matrix[0].length;boolean flagCol0 false;for (int i 0; i m; i) {if (matrix[i][0] 0) {flagCol0 true;}for (int j 1; j n; j) {if (matrix[i][j] 0) {matrix[i][0] matrix[0][j] 0;}}}for (int i m - 1; i 0; i--) {for (int j 1; j n; j) {if (matrix[i][0] 0 || matrix[0][j] 0) {matrix[i][j] 0;}}if (flagCol0) {matrix[i][0] 0;}}}
}时间复杂度 O(mn)其中m是矩阵的行数n是矩阵的列数。我们至多只需要遍历该矩阵两次。 空间复杂度 O(1)。我们只需要常数空间存储若干变量。
