162. 矩阵归零先找为零的位置，再分别置零

和蔼的zhxing

发布于 2018-09-04 11:20:46

6150

发布于 2018-09-04 11:20:46

给定一个m×n矩阵，如果一个元素是0，则将其所在行和列全部元素变成0。需要在原矩阵上完成操作。

样例给出一个矩阵

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

[
  [0, 2],
  [0, 0]
]

先找为零的位置，再分别置零

一种显而易见的方法是先找到为零的位置，把这些位置记下来，然后根据这些位置来进行进行一整行或者一整列清除。记录位置的时候可以用vector<pair<int,int>>来一组一组来记录，这样是最直观的。我一开始的程序也是这么写的，没有什么问题。后来发现，如果某一行或者某一列出现多个0的话，上面的方法没有避免重复，可能在前面的操作中都已经清零过了，所以想到可以吧row和col分别用一个set来记录，顺便去重，然后分别遍历两个set，这样就可以保证不做重复的事情，不出意外程序快乐1/3左右。两个版本的程序我都保留贴在下面：

    /*
    //使用pair的主程序
    void setZeroes(vector<vector<int>> &matrix) {
        vector<pair<int,int>> ZerosPos;
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                if(matrix[i][j]==0)
                ZerosPos.push_back(make_pair(i,j));
            }
        }
        for(auto zp:ZerosPos)
        {
            setZeroR(matrix,zp.first);
            setZeroC(matrix,zp.second);
        }
        
        // write your code here
    }
    */
  //使用set的主程序
    void setZeroes(vector<vector<int>> &matrix) {
        set<int> row;
        set<int> col;
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                if(matrix[i][j]==0)
                {row.insert(i);
                col.insert(j);
                }
            }
        }
        for(auto r:row) setZeroR(matrix,r);
        for(auto c:col)  setZeroC(matrix,c);
        
        
        // write your code here
    }
    static void setZeroR(vector<vector<int>> &mat,int row)
    {
        mat[row]=vector<int>(mat[row].size(),0);      //整行直接置零
    } 
    static void setZeroC(vector<vector<int>> &mat,int col)
    {
        for(int i=0;i<mat.size();i++)
        mat[i][col]=0;             //这一列置零，因为在不同的vector<int>中，所以只能这么一个一个做。
    }

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018.02.28 ，如有侵权请联系 cloudcommunity@tencent.com 删除

int