矩阵归零

红太狼 2021-04-24 14:56 515阅读 0赞

##题目：##

给定一个m×n矩阵，如果一个元素是0，则将其所在行和列全部元素变成0。  
需要在原矩阵上完成操作。

##样例：##

给出一个矩阵  
[  
[1, 2],  
[0, 3]  
]  
返回  
[  
[0, 2],  
[0, 0]  
]

> ###思路：###
> 
>  *  如果使用额外的空间的话，需要两个一维数组，分别标记哪一行哪一列有0，然后把这些行和列都清0即可。这样空间复杂度为O(m+n);
>  *  但是题目要求在原矩阵上完成操作，所以空间复杂度应该为O(1)；于是把第一行和第一列作为标记。  
>     首先，先判断第一行第一列是否含有0，并用两个bool变量记录起来。  
>     然后，遍历其他行和列，如果有0，**把第一列的该行置0，把第一行的该列置为0，**例如matrix[2] [3]为0，那么需要将matrix[2] [0]和matrix[0] [3]置0。  
>     再次，遍历第一行和第一列的元素，如果有0，则其所在行和列置0，不包括第一行第一列。  
>     最后，根据前面的bool标记判断是否把第一行和第一列置零。  
>     注意一下：第一列清零，是每一行清零，是行的数目。

##参考答案：##

class Solution {
    public:
        /*
         * @param matrix: A lsit of lists of integers
         * @return: 
         */
        void setZeroes(vector<vector<int>> &matrix) {
            // write your code here
            if(matrix.empty())  return;
            int m = matrix.size();
            int n = matrix[0].size();
            bool row = false;
            bool column = false;
            //遍历第一列的每一行
            for(int i=0 ; i<m; i++){
                if(matrix[i][0] == 0){
                    column = true;
                    break;
                }
            }
            //遍历第一行的每一列
            for(int i=0; i<n; i++){
                cout<<n<<endl;
                if(matrix[0][i] == 0){
                    row = true;
                    break;
                }
            }
            
            for(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;
                    }
                }
            }
            /*
            for(int i=1; i<m; i++){
                if(matrix[i][0] == 0){
                    for(int j=1; j<n; j++){
                        matrix[i][j] = 0;
                    }
                }
            }
            for(int i=1; i<n; i++){
                if(matrix[0][i] == 0){
                    for(int j=1; j<m; j++){
                        matrix[j][i] = 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;
                    }
                }
            }
            //row为真的话，代表第一行有0，将行清零，注意下是每列操作
            if(row){
                for(int i=0; i<n; i++){
                    matrix[0][i] = 0;
                }
            }
            //column为真的话，代表第一列有0,将列清零，注意下是每行操作
            if(column){
                for(int i=0 ;i<m; i++){
                    matrix[i][0] = 0;
                }
            }
            
        }
    };