[leetcode] 73. Set Matrix Zeroes解題レポート

タイトルリンク:https://leetcode.com/problems/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.
click to show follow up.
Follow up:
Did you use extra space? A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution?
考え方:O(m+n)を使う時間の複雑さは比較的やりやすい.
コードは次のとおりです.

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m=matrix.size(), n=matrix[0].size(), flagRow[m], flagCol[n];
        memset(flagRow, 1, sizeof(flagRow));
        memset(flagCol, 1, sizeof(flagCol));
        for(int i = 0; i< m; i++)//  
            for(int j =0; j< n; j++)
            {
                if(flagRow[i] == 0 && flagCol[j] == 0)
                    continue;
                if(matrix[i][j] == 0)
                {
                    flagRow[i] = 0;
                    flagCol[j] = 0;
                }
            }
        for(int i = 0; i< m; i++)//      0
        {
            if(flagRow[i] == 0)
                for(int j =0; j< n; j++)
                    matrix[i][j] = 0;
        }
        for(int i = 0; i< n; i++)//      0
        {
            if(flagCol[i] == 0)
                for(int j = 0; j < m; j++)
                    matrix[j][i] = 0;
        }
    }
};

しかし,この問題は後で定数の空間複雑度を用いることが要求され,配列自体の空間を利用してマークしなければならない.現在の行と列がクリアされるべきかどうかを記録するタグとして、最初の行と最初の行を選択できます.まず、最初の行と最初の列がクリアされるべきかどうかをチェックし、クリアされるべきであれば、最後にクリアされます.
コードは次のとおりです.

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int flagRow=false, flagCol=false,m=matrix.size(), n=matrix[0].size();
        for(int i =0; i < m; i++)//           0
            flagCol = (matrix[i][0]==0)?true:flagCol;
        for(int i =0; i < n; i++)//           0
            flagRow = (matrix[0][i]==0)?true:flagRow;
        for(int i =1; i< m; i++)
            for(int j =1; j< n; j++)
            {
                matrix[i][0] = (matrix[i][j]==0)?0:matrix[i][0];//     0，      0
                matrix[0][j] = (matrix[i][j]==0)?0:matrix[0][j];//     0，      0
            }
        for(int i = 1; i < m; i++)
            for(int j =1; j< n; j++)
                if(!matrix[i][0] || !matrix[0][j])//       0，    0
                    matrix[i][j] = 0;
        if(flagCol)//          0
            for(int i =0; i< m; i++)
                matrix[i][0] = 0;
        if(flagRow)//          0
            for(int i = 0; i< n; i++)
                matrix[0][i] = 0;
    }
};

第2の方法の参照:http://fisherlei.blogspot.com/2013/01/leetcode-set-matrix-zeroes.html