题目描述

• 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.
Follow up:
Did you use extra space?
A straight forward solution using O(m n) 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?

题目大意

题目的意思就是，给定一个矩阵，如果矩阵中某个位置的数是0，就把该位置所在的行和列全部置为0。

思路

使用第一行和第一列来记录行和列的置0情况（例如matrix[2][3]是0，就把matrix[0][3]和matrix[2][0]置为0）。

首先，遍历第一行和第一列，看是否原先就有0，用两个bool变量来标识，如果原先就有0，最后要把有0的第一行或者第一列置为0。

然后，用第一行和第一列来记录行和列的置0情况，为什么能这样做呢，因为假如matrix[i][j]为0，最终总要把matrix[i][0]和matrix[0][j]置为0。

然后，遍历这个二维数组，如果发现matrix[i][0]或者matrix[0][j]为0，就把matrix[i][j]置为0。

这样的做法只需要两个额外变量（即，来标识第一行或者第一列是否有0的两个bool值），所以空间复杂度是O(1)。
时间上需要进行两次扫描，一次确定行列置0情况，一次对矩阵进行实际的置0操作，所以总的时间复杂度是O(m*n)

代码

#include<iostream>
#include<vector>
using namespace std;

void setZeroes(vector<vector<int> > &matrix)
{
    int rows = matrix.size(); // 行数
    if(rows == 0)return;
    int cols = matrix[0].size(); // 列数
    if(cols == 0)return;

    bool r0 = false; // 标识第一行是否有0
    for(int i=0; i<cols; i++)
    {
        if(matrix[0][i] == 0)
        {
            // cout<<0<<' '<<i<<endl;
            r0 = true;
            break;
        }
    }

    bool c0 = false; // 标识第一列是否有0
    for(int i=0; i<rows; i++)
    {
        if(matrix[i][0] == 0)
        {
            // cout<<i<<' '<<0<<endl;
            c0 = true;
            break;
        }
    }

    // 用第一行第一列来记录0的情况
    for(int i=1; i<rows; i++)
    {
        for(int j=1; j<cols; j++)
        {
            if(matrix[i][j] == 0)
            {
                // cout<<i<<' '<<j<<endl;
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    // 将存在0的所在的行和列都置为0
    for(int i=1; i<rows; i++)
    {
        for(int j=1; j<cols; j++)
        {
            if(matrix[i][0]==0 || matrix[0][j]==0)
            {
                matrix[i][j] = 0;
                // cout<<i<<' '<<j<<endl;
            }
        }
    }

    // 若第一行有0，就把第一行全部置为0
    if(r0 == true)
    {
        // r0==true，说明第一行有0，每行有cols列，所以循环cols次
        for(int i=0; i<cols; i++)
        {
            matrix[0][i] = 0;
        }
    }

    // 若第一列有0，就把第一列全部置为0
    if(c0 == true)
    {
        // c0==true，说明第一列有0，每行有rows列，所以循环rows次
        for(int i=0; i<rows; i++)
        {
            matrix[i][0] = 0;
        }
    }
}

int main()
{
    int a[5][4]={
        {0, 2, 0, 4},
        {2, 1, 3, 1},
        {1, 8, 9, 7},
        {9, 8, 7, 4}
    };

    vector<vector<int > > matrix(4);

    for(int i=0; i<4; i++)
    {
        for(int j=0; j<4; j++)
        {
            matrix[i].push_back(a[i][j]);
        }
    }

    setZeroes(matrix);

    for(int i=0; i<4; i++)
    {
        for(int j=0; j<4; j++)
        {
            cout<<matrix[i][j]<<' ';
        }
        cout<<endl;
    }

    return 0;
}

运行结果

以上。