地方网站域名用全拼,西安建设工程交易信息网,安阳县职业中等专业学校,网站制作性价比哪家好矩阵置零
给定一个 m x n 的矩阵#xff0c;如果一个元素为 0 #xff0c;则将其所在行和列的所有元素都设为0 。请使用 原地 算法。在计算机科学中#xff0c;一个原地算法#xff08;in-place algorithm#xff09;是一种使用小的#xff0c;固定数量的额外之空间来转…矩阵置零
给定一个 m x n 的矩阵如果一个元素为 0 则将其所在行和列的所有元素都设为0 。请使用 原地 算法。在计算机科学中一个原地算法in-place algorithm是一种使用小的固定数量的额外之空间来转换资料的算法。当算法执行时输入的资料通常会被要输出的部分覆盖掉。不是原地算法有时候称为非原地not-in-place或不得其所out-of-place。输入二维数组 输出二维数组 思路
方法一使用两个标记数组 两个标记数组分别记录每一行和每一列是否有零出现如果出现则将对应的标记数组置为true最后再次遍历数组用标记数组更新原数组即可
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];//对标记数组进行赋值for(int i 0;i m;i){for(int j 0;j n;j){if(matrix[i][j] 0){row[i] col[j] true;}}}//再次遍历,只要有一个标记为true则置为0for(int i 0;i m;i){for(int j 0;j n;j){if(row[i] || col[j]){matrix[i][j] 0;}}}}
}方法二使用两个标记变量 使用矩阵的第一列和第一行去代替方法一中的标记数组但是第一行和第一列的数值也会因此而改变所以使用两个标记变量来第一行和第一列中原本是否包含0
class Solution {public void setZeroes(int[][] matrix) {//用变量定义数组的行和列的长度方便写代码int m matrix.length;int n matrix[0].length;//定义标记变量boolean firstRow false;boolean firstCol false;//对标记变量进行赋值for(int i 0;i m;i){if(matrix[i][0] 0){firstCol true;}}for(int i 0;i n;i){if(matrix[0][i] 0){firstRow 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(firstCol){for(int i 0;i m;i){matrix[i][0] 0;}}if(firstRow){for(int i 0;i n;i){matrix[0][i] 0;}}}
}方法三使用一个标记变量 第一列的第一个元素即可以标记第一行是否出现0。但为了防止每一列的第一个元素被提前更新我们需要从最后一行开始倒序地处理矩阵元素。
class Solution {public void setZeroes(int[][] matrix) {//用变量定义数组的行和列的长度方便写代码int m matrix.length;int n matrix[0].length;//定义标记变量boolean firstColAndRow false;//对标记变量进行赋值for(int i 0; i m; i){if(matrix[i][0] 0){firstColAndRow 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(firstColAndRow){matrix[i][0] 0;}}}
}
