leetcode题目链接
这道题因为要求在O(1)的空间复杂度下面完成,所以最好的情况就是利用矩阵本身有的元素进行代码编写,而不另外开辟空间。
所以思路如下:
1.遍历第一行第一列,观察是否需要置0,并用变量记录
2.再次遍历矩阵,根据第一行和第一列的标记来置零。
3.根据之前变量的结果,处理第一行第一列、
class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m=matrix.size();int n=matrix[0].size();bool firstRowZero=false;bool firstColZero=false;//检查第一列是否需要置0for(int i=0;i<m;++i){if(matrix[i][0]==0){firstColZero=true;}}//检查第一行是否需要置0for(int j=0;j<n;++j){if(matrix[0][j]==0){firstRowZero=true;}}//查询剩余的行列,如果有0则其当前行的第一个元素和当前列的第一个元素都变成0for(int i=1;i<m;++i){for(int j=1;j<n;++j){if(matrix[i][j]==0){matrix[i][0]=0;matrix[0][j]=0;}}}//开始将需要置0的所有元素变成0for(int i=1;i<m;++i){if(matrix[i][0]==0){for(int j=1;j<n;++j){matrix[i][j]=0;}}}for(int j=1;j<n;++j){if(matrix[0][j]==0){for(int i=1;i<m;++i){matrix[i][j]=0;}}}//处理第一行和第一列if(firstRowZero){for(int i=0;i<n;++i){matrix[0][i]=0;}}if(firstColZero){for(int j=0;j<m;++j){matrix[j][0]=0;}}}
};
详细解释
标记第一行和第一列:
检查第一列和第一行是否有零,记录下来,以便最后处理。
遍历矩阵的其余部分,如果某个元素为零,则将该元素所在的行首和列首标记为零。
根据标记置零:
根据第一行和第一列的标记,将相应的行和列置零。
处理第一行和第一列:
根据初始记录,处理第一行和第一列的置零。