程序员面试金典1.7 清除行列

题目描述

请编写一个算法，若N阶方阵中某个元素为0，则将其所在的行与列清零。

给定一个N阶方阵int[][](C++中为vector<>>)mat和矩阵的阶数n，请返回完成操作后的int[][]方阵(C++中为vector<>>)，保证n小于等于300，矩阵中的元素为int范围内。

测试样例：

[[1,2,3],[0,1,2],[0,0,1]]

返回：[[0,0,3],[0,0,0],[0,0,0]]

链接：https://www.nowcoder.com/questionTerminal/c95aac1506574dfc8ad44c3939c6739d
来源：牛客网

思路1，就是采用两个bool型数组，记录下有0 的行和列。然后分别清除行和列。
时间复杂度0（n^2），但是遍历了两遍，空间复杂度0（n）；
下面的方法2，空间复杂度进一步降低，只要两个变量解决问题,空间复杂度0（1）。*/
class Clearer {
public:
    vector<vector<int> > clearZero(vector<vector<int> > mat, int n) {
        // write code here
        if(mat.size()<=0) return mat;
        //记录行和列的0
        bool* row=new bool[mat.size()];
        bool* col=new bool[mat[0].size()];
        //初始化一下
        for(unsigned int i=0;i<mat.size();i++)
            row[i]=false;
        for(unsigned int i=0;i<mat[0].size();i++)
            col[i]=false;
        //第一遍遍历元素，统计并标记0的行、列；
        for(unsigned int i=0;i<mat.size();i++)
        {
            for(unsigned int j=0;j<mat[0].size();j++)
            {
                if(mat[i][j]==0)
                {
                    row[i]=true;
                    col[j]=true;
                }
            }
        }
        //对应的位置置为0
        for(unsigned int i=0;i<mat.size();i++)
        {
            for(unsigned int j=0;j<mat[0].size();j++)
            {
                if(row[i]||col[j])
                    mat[i][j]=0;
            }
        }
        return mat;
    }
};

首先说下：vector<vector<int> > mat,

mat：表示二维数组，

//10行，5列

vector<vector<int>> a(10, vector<int>(5));

cout << "行"<< a.size() << endl;

cout << "列" << a[0].size() << endl;

cout << "列" << a[1].size() << endl;

//a[].size()表示列，括号里，添几都是一样的，因为列数一样。