网站做301打不开/产品网络营销策划方案

Set Matrix Zeroes

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

 

空间复杂度O(1)，不能使用额外的空间，那得多重复几次。

1. 判断第一行和第一列是否有0，用于最后对第一行和第一列赋值；
2. 将除掉第一行和第一列的[m-1,n-1]映射到第一行和第一列保存，如果matrix[i][j]=0那么matrix[0][j]=0,matrix[i][0]=0；
3. 将第一行和第一列赋值。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if(matrix.size()==0 || matrix[0].size()==0) return;
        int m=matrix.size(),n=matrix[0].size();
        bool firstRowZero=false,firstColZero=false;
        for(int i=0;i<m;i++)
        {
            if(matrix[i][0]==0)
            {
                firstColZero = true;
                break;
            }
        }
        for(int j=0;j<n;j++)
        {
            if(matrix[0][j]==0)
            {
                firstRowZero = true;
                break;
            }
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(matrix[i][j]==0)
                {
                    matrix[0][j]=0;
                    matrix[i][0]=0; 
                }
            }
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(matrix[0][j]==0 || matrix[i][0]==0)
                {
                    matrix[i][j]=0;
                }
            }
        }
        if(firstRowZero)
        {
            for(int j=0;j<n;j++) matrix[0][j]=0;
        }
        if(firstColZero)
        {
            for(int i=0;i<m;i++) matrix[i][0]=0;
        }
    }
};