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

由于要求”do it in place”,所以也就是说要求我们只能用O(1)的空间复杂度。

这道题目一个错误的想法是看到了就直接把行列归0,其实这样是错误的,如果我们对矩阵从左上到右下遍历,该0所在行归零会影响遍历其所在的列的值,而这些之后行上的数据如果原本是1,相当于我们改变了原始数据,这样再进行判断肯定是错误的。(e.g. [[1,1,0] , [1,1,1]], 如果看到就归零会变成[[0,0,0],[0,0,0]],因为第一行的0会改变第二行的第三个0,而它应该是1)。

我们需要地方记录数据,而且又不能影响元数据。这个矩阵有个很明显的特点就是后面遍历的不会对之前遍历的数据的最终结果有影响(先出0后出0,反正那行肯定是0), 所以很自然的选择第一行来进行记录。第一步记录是否有如果某个位置(i, j)是0,则将第一行改为0,并记录该行归0,直到达到该行末尾,再对此行进行归0处理(如果之前的记录是0),这样就不会对后排和后列数据造成影响。等到遍历完成,则根据第一行的数组,将每行在该列的数字归零。最后记得根据最初的记录处理第一行看是否归0.

Solution


void setZeroes(int** matrix, int matrixRowSize, int matrixColSize) {
        bool firstRowZero = false, ifZero = false;
    
        for(int i = 0; i < matrixRowSize; ++i)
        {
                ifZero = false;
                for(int j = 0; j < matrixColSize; ++j)
                {
                        if(matrix[i][j] == 0)
                        {
                                if(i == 0) firstRowZero = true;
                                else
                                {
                                        ifZero = true;
                                        matrix[0][j] = 0;
                                }
                        }
                }
                if(ifZero)
                for(int j = 0; j < matrixColSize; ++j)  matrix[i][j] = 0;
        }
        for(int j = 0; j < matrixColSize; ++j)
        {
                if(matrix[0][j] == 0)
                {
                        for(int i = 0; i < matrixRowSize; ++i)
                        matrix[i][j] = 0;
                }
        }
        if(firstRowZero)
                for(int j = 0; j < matrixColSize; ++j) matrix[0][j] = 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *