一. 数组_二维数组变换_73. 矩阵置零
链接：
输入： = [[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]]
这里首先遍历矩阵，将对应的为0的值，将对应的i和j加入到map中
在迭代map，将对应的行和列置位0
这里除了map也可以使用数组（桶排序的方式），但是浪费空间大于map，且浪费的空间大于map
这里的时间复杂度：O(mn)，空间复杂度：O(m+n)
void setZeroes(vector<vector<int>>& matrix) {unordered_map<int, int> map_r;unordered_map<int, int> map_c;int m = matrix.size();int n = matrix[0].size();//将其元素为0对应的行和列置位1for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(matrix[i][j] == 0) {map_r[i] = 1;map_c[j] = 1;}}}unordered_map<int, int>::iterator iter;//这里将对应的行置位0for(iter = map_r.begin(); iter != map_r.end(); iter++) {//对应着key和value、iter->first和iter->secondfor(int i = 0; i < n; i++) {matrix[iter->first][i] = 0;}}//这里将对应的列置位0for(iter = map_c.begin(); iter != map_c.end(); iter++) {//对应着key和value、iter->first和iter->secondfor(int i = 0; i < m; i++) {matrix[i][iter->first] = 0;}}
}
void setZeroes(vector<vector<int>>& matrix) {int m = matrix.size();int n = matrix[0].size();vector<int> row(m), column(n);for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(matrix[i][j] == 0) {row[i] = 1; //row矩阵的i位置置位1，也就是i行为0column[j] = 1; //j列为0}}}//上面使用数组标记了，对应行和列为0//下面遍历，若是对应的行或列有一个为0的，那么就为0for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(row[i] || column[j]) {matrix[i][j] = 0;}}}
}
参考官方题解，这个想法很巧妙，原地操作，当不能连续的进行的时候，一般就需要用数组中的空间来代替
1.这里我们使用第一行（该列是否置位0,0是需要）和第一列（该行是否需要置位0,0是需要）
2.这样原来第一行和第一列的0也可以保存下来，如果使用第一行和第二行，那么原来的元素还要考虑到
3.原来的需要考虑的内容很多，而且容易出错，不如用第一行和第一列，这样原来当前的行和列直接保留即可
4.这里(0,0)需要抛弃，第一行和第一列需要提前使用标量进行标记
5.遍历除了第一行和第一列的元素，更新第一行和第一列
6.使用第一行和第一列更新剩下的元素
7.使用标识变量更新第一行和第一列
虽然感觉算法空间复杂度降低了，但是在运行的时候，空间返回还上升了。
时间变慢了，相对于上一个方法，这个可能运行大量的数据集才能体现出差别吧。
void setZeroes(vector<vector<int>>& matrix) {int m = matrix.size();int n = matrix[0].size();bool f_row = false, f_column = false;//第一行标识对应的列为0，第一列标识对应的行为0//当对应的值为0，则对应的列和行应该为0//标识第一行的标识值//如果一个位置是0的话，那么有行标识和列标识，而对于第一行，行标识已经记录，列标识不需要处理for(int i = 0; i < n; i++) {if(!matrix[0][i]) {f_row = true;break;}}//标识第一列的标识值for(int i = 0; i < m; i++) {if(!matrix[i][0]) {f_column = true;break;}}//遍历除了第一行和第一列的所有元素，更新到第一行和第一列//在写代码的时候我又想到了另外的问题，如果该列有0那么更新了第一行元素，而第一行元素，如果没有0的话，那//会不会影响原来的值，回来我想明白了，如果该行该列有0，那么第一行和第一列对应的位置必定是0，所以不会影响的。for(int i = 1; i < m; i++) {for(int j = 1; j < n; j++) {if(!matrix[i][j]) {matrix[i][0] = matrix[0][j] = 0;}}}//根据第一行和第一列的值更新剩下的元素for(int i = 1; i < m; i++) {for(int j = 1; j < n; j++) {if(!matrix[i][0] || !matrix[0][j]) {matrix[i][j] = 0;}}}//根据第一行和第一列的标志变量更新第一行和第一列的值if(f_row) {for(int i = 0; i < n; i++) {matrix[0][i] = 0;}}if(f_column) {for(int i = 0; i < m; i++) {matrix[i][0] = 0;}}
}
只是用一个标记变量标识
1.首先检查第一列是否有0，有的话，标识
2.检查第一行是否有0，有的话[0][0]=0，这个有先后关系，必须先检查列，再检查行
3.和上面一样，利用当前值更新第一行和第一列，利用第一行和第一列更新当前值
4.首先检查[0][0]更新第一行，之后在更新第一列，这个也有顺序。
这里[0][0]标记行和标记列都是可以的，唯一的不同是，这里标记行，行就要后记录，先处理，标记列，列就要被优先处理
否则会被影响。
void setZeroes(vector<vector<int>>& matrix) {int m = matrix.size();int n = matrix[0].size();bool f_column = false;//第一列是否有0检查for(int i = 0; i < m; i++) {if(!matrix[i][0]) {f_column = true;break;}}//第一行是否有0检查for(int i = 0; i < n; i++) {if(!matrix[0][i]) {matrix[0][0] = 0;}}//遍历除了第一行和第一列之外的所有行，标记for(int i = 1; i < m; i++) {for(int j = 1; j < n; j++) {if(!matrix[i][j]) {matrix[i][0] = matrix[0][j] = 0;}}}//根据第一行和第一列的标识，更新其他元素for(int i = 1; i < m; i++) {for(int j = 1; j < n; j++) {if(!matrix[i][0] || !matrix[0][j]) {matrix[i][j] = 0;}}}//更新第一行//这里若是第一行的第二个元素到最后一个元素有0，那么会让其赋值为0//或者本身这个位置就是0if(!matrix[0][0]) {for(int i = 0; i < n; i++) {matrix[0][i] = 0;}}if(f_column) {for(int i = 0; i < m; i++) {matrix[i][0] = 0;}}
}
这里官方的题解，可以拆成上面的样子，但是官方的题解要考虑的内容很多，而且编程技巧很足
多个for循环，组合成一个for循环。
检查可以分为首先进行第一列检查，之后，在进行第一行检查完成之后，在进行剩下行的检查，虽然写在一个for循环里面，但是又先后顺序
在置位0的时候也是有顺序的，先从最后一行开始置位0，先根据第一行和第一列更新内部，之后，倒着更新，当更新到第一行的时候，根据[0][0]的位置更新
对于第一列，根据更新
