73. 矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1:

输入:  [   [1,1,1],   [1,0,1],   [1,1,1] ] 输出:  [   [1,0,1],   [0,0,0],   [1,0,1] ] 示例 2:

输入:  [   [0,1,2,0],   [3,4,5,2],   [1,3,1,5] ] 输出:  [   [0,0,0,0],   [0,4,5,0],   [0,3,1,0] ]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/set-matrix-zeroes

先解决问题再考虑优化。

常规思路，分别用2个额外数组来记录哪一行哪一列需要处理。LeetCode现在改了，数组初始化不太好用(加个头文件也可以用memset，#include<string.h>)，一年前的代码没法通过了都，还得自己写for循环初始化，我就用set这个数据结构了。

class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m=matrix.size(); if(m>0) { int n=matrix[0].size(); // int row[m]={0},col[n]={0}; // memset(row,0,sizeof(row)); // int row[m],col[n]; // for(int i=0;i<m;i++) // row[i]=0; // for(int i=0;i<n;i++) // col[i]=0; set<int> row,col; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(matrix[i][j]==0) { // row[i]=1; // col[j]=1; row.insert(i); col.insert(j); } } } for(int i:row) { for(int j=0;j<n;j++) { matrix[i][j]=0; } } for(int i:col) { for(int j=0;j<m;j++) { matrix[j][i]=0; } } } } };

空间复杂度O(1）

用数组第一行第一列来记录

matrix[i][0]=0;//i行全部置0 matrix[0][j]=0;//j列全部置0

但是在置零时，第一行第一列都先不处理（它们是我们的处理的根据，最后再处理，不然就破坏了根据），因为如果第一行需要置零，例如上图中1,2都被置0，结果到处理列时，第2,3两列都被置零了，这样就错了。所以第一行和第一列置0放在后面处理。

class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m=matrix.size(); if(m>0) { int n=matrix[0].size(); bool row=false,col=false; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(matrix[i][j]==0) { if(i==0) { row=true; } if(j==0) { col=true; } matrix[i][0]=0;//i行全部置0 matrix[0][j]=0;//j列全部置0 } } } for(int i=1;i<m;i++) { if(matrix[i][0]==0) { for(int j=0;j<n;j++) { matrix[i][j]=0; } } } for(int j=1;j<n;j++) { if(matrix[0][j]==0) { for(int k=0;k<m;k++) { matrix[k][j]=0; } } } if(row) { for(int i=0;i<n;i++) { matrix[0][i]=0; } } if(col) { for(int i=0;i<m;i++) { matrix[i][0]=0; } } } } };