您的位置:首页 > 新闻 > 会展 > 网站建设加优化_方维服务客户类型_南通企业网站制作_外包公司值得去吗

网站建设加优化_方维服务客户类型_南通企业网站制作_外包公司值得去吗

2025/2/24 4:43:42 来源:https://blog.csdn.net/qq_46103963/article/details/145754852  浏览:    关键词:网站建设加优化_方维服务客户类型_南通企业网站制作_外包公司值得去吗
网站建设加优化_方维服务客户类型_南通企业网站制作_外包公司值得去吗

矩阵置零

给定一个 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;}}}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com