描述

在一个mxn的矩形中，设置矩形中的0元素所在的行、列的元素都设置为0，在原地执行这种操作。

在实现需求时是否使用了额外空间？直观的方法是使用O(mxn)的额外空间，在改进一步就是使用O(m+n)的空间，但是还不是最好的方法，是否可以只使用常量级别的额外空间呢。

分析

简单的方法是记录所有的0元素所在的行列，然后再根据记录设置行列的元素都为0即可，这样需要O(m+n)的空间。

代码实现如下:

void setMatrixZeros00(vector<vector<int>>& matrix)
{
    vector<int> zeroRows;
    vector<int> zeroCols;
    
    size_t m = matrix.size();
    size_t n = matrix[0].size();
    
    for(int i=0; i<m; ++i) {
        for (int j=0; j<n; ++j) {
            if (matrix[i][j] == 0) {
                zeroRows.push_back(i);
                zeroCols.push_back(j);
            }
        }
    }
    
    // 设置为0
    for (size_t i=0, cnt = zeroRows.size(); i<cnt; ++i) {
        fill(&matrix[zeroRows[i]][0], &matrix[zeroRows[i]][0]+n, 0);
    }
    
    for(size_t i=0, cnt=zeroCols.size(); i<cnt; ++i) {
        for(int j=0; j<m; j++) {
            matrix[j][zeroCols[i]] = 0;
        }
    }
}

使用常量空间的方法是借助辅助位，选定一行一列做为参考，为了遍历的方便性选择第一行第一列做为辅助元素：

1，记录第一行、第一列是否有0元素；

2，从辅助行列的下一行、下一列开始遍历元素，如果元素为0，则设置元素所在列的第一行、所在行的第一列的元素为0；

3，从辅助行列的下一行、下一列开始遍历元素，如果遍历元素的第一行的此列、第一列此行的元素为0，则设置此元素为0；

4，如果第一行、第一列起始时即存在0元素，则设置第一行、第一列所有元素为0；

实现如下：

//Time : O(mxn) Space : O(1)
void setMatrixZeros01(vector<vector<int>>& matrix)
{
    size_t m = matrix.size();
    size_t n = matrix[0].size();
    
    // 记录第1行、第1列是否有0
    bool zeroInFirstRow = false;
    bool zeroInFirstCol = false;
    
    for (size_t i=0; i<n; ++i) {
        if (matrix[0][i] == 0) {
            zeroInFirstRow = true;
            break;
        }
    }
    
    for (size_t i=0; i<m; ++i) {
        if (matrix[i][0] == 0) {
            zeroInFirstCol = true;
            break;
        }
    }
    
    // 从第二行、第二列开始遍历
    for(size_t i=1; i<m; ++i){
        for(size_t j=1; j<n; ++j) {
            if (matrix[i][j] == 0) {
                matrix[0][j] = 0;
                matrix[i][0] = 0;
            }
        }
    }
    
    // 进行第二次遍历，若某一个数对应的第一行中此列位置为0 或者 对应此数的第一列中此行位置的数字为0则设置为0
    for(size_t i=1; i<m; ++i) {
        for (size_t j=1; j<n; ++j) {
            if (matrix[0][j]==0 || matrix[i][0]==0) {
                matrix[i][j] = 0;
            }
        }
    }
    
    // 进行第一行、第一列的操作
    if (zeroInFirstRow) {
        fill(&matrix[0][0], &matrix[0][0]+m, 0);
    }
    
    if (zeroInFirstCol) {
        for(size_t i=0; i<m; ++i) {
            matrix[i][0] = 0;
        }
    }
}