首页 > 代码库 > leetcode第一刷_Set Matrix Zeroes
leetcode第一刷_Set Matrix Zeroes
这个题乍一看很简单,实际上还挺有技巧的。我最开始的想法是找一个特殊值标记,遇到一个0,把他所对应的行列中非零的元素标记成这个特殊值,0值保持不变,然后再从头遍历一次,碰到特殊值就转化成0。
问题是这个特殊值怎么确定,题目中没有把取值范围给出,我怀着侥幸的心理用了最大和最小的int,都被揪了出来。。如果找一个不存在于数组中的值,这个复杂度太高了。
有没有其他更好的方法呢?当然有。这个思想很巧妙,最后的结果是把所有0所在的行列都化成0,换句话说,化成0这个事情只要标记出是哪一行以及哪一列就可以了,能不能找到一种标记的方式来完成这个事情呢?做法是如果扫描到一个0,我们就把这个数的行列第一个数值置成0,用来做标记位,等全部扫描完毕后,针对为第一行和第一列为0的那些行列,置成0就可以了。
有一个细节,第一行和第一列该怎么办,他们可能一开始并没有0,因为标记的原因有0了,怎么区分呢?处理方式其实很简单,一开始先看一下它含不含0,然后在最后根据这个结果来决定要不要把他们变成0.
class Solution { public: void setZeroes(vector<vector<int> > &matrix) { int row = matrix.size(), column = matrix[0].size(); bool firstRow = false, firstColumn = false; for(int i=0;i<row;i++) if(matrix[i][0] == 0){ firstColumn = true; break; } for(int i=0;i<column;i++) if(matrix[0][i] == 0){ firstRow = true; break; } for(int i=1;i<row;i++){ for(int j=1;j<column;j++){ if(matrix[i][j] == 0){ matrix[i][0] = 0; matrix[0][j] = 0; } } } for(int i=1;i<row;i++){ for(int j=1;j<column;j++){ if(matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0; } } if(firstRow){ for(int i=0;i<column;i++) matrix[0][i] = 0; } if(firstColumn){ for(int i=0;i<row;i++) matrix[i][0] = 0; } } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。