首页 > 代码库 > LeetCode: Set Matrix Zeroes [073]

LeetCode: Set Matrix Zeroes [073]

2024-07-06 13:54:29   225人阅读

【题目】


Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.



【题意】

    给定一个mXn的矩阵，如果其中的元素为0，则对应的行和列都用0填充。
    不能申请额外的空间。


【思路】

       

        第一行和第一列空出来标记需要置0的列和行


        第一遍扫描：
        扫描第一行，判断第一行是否需要清零
        扫描第一列，判断第一列是否需要清零
        扫描[1,1]~[m-1, n-1]的区块，如果某个位置上的值为0，则其对应的行和列在第一行相应位置做上标记（第一行和第一列相应位置置0即可）
        
        在完成第一遍的扫描之后，
        
        扫描第一行除[0,0]外的所有位置，如果某个位置上是0，则对应的列清0
        扫描第一列除[0,0]外的所有位置，如果某个位置上是0，则对应的行清0


第一行清零（根据一开始的判断看是否清零）

第一列清零（根据一开始的判断看是否清零）


【代码】

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        int rows=matrix.size();
        if(rows==0)return;
        int cols=matrix[0].size();
        if(cols==0)return;
        
        bool isR1Removed=false;
        bool isC1Removed=false;
        // 判断第1行是否需要清零
        for(int j=0; j<cols; j++){
            if(matrix[0][j]==0){isR1Removed=true;break;}
        }
        // 判断第1列是否需要清零
        for(int i=0; i<rows; i++){
            if(matrix[i][0]==0){isC1Removed=true;break;}
        }
        
        //扫描除第一行第一列之外的区域，并在第一行和第一列做相应的清零标记
        for(int i=1; i<rows; i++){
            for(int j=1; j<cols; j++){
                if(matrix[i][j]==0){
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
            }
        }
        
        //扫描第一行，相应列清零
        for(int j=1; j<cols; j++){
            if(matrix[0][j]==0){
                for(int i=1; i<rows; i++){
                    matrix[i][j]=0;
                }
            }
        }
        //扫描第一列，相应行清零
        for(int i=1; i<rows; i++){
            if(matrix[i][0]==0){
                for(int j=1; j<cols; j++){
                    matrix[i][j]=0;
                }
            }
        }
        if(isR1Removed){
            //第一行清0
            for(int j=0; j<cols; j++) matrix[0][j]=0;
        }
        if(isC1Removed){
            //第一列清0
            for(int i=0; i<rows; i++) matrix[i][0]=0;
        }

    }
};


联系
我们